Вычислительные методы алгебры (лекции) §1. Учет погрешностей вычислений. При решении математических задач могут возникнуть погрешности по различным причинам: При составлении математической модели физического процесса или явления приходится принимать условия, упрощающие постановку задачи. Поэтому математическая модель не отражает реальный процесс, а дает его идеализированную картину. Погрешность, возникающая при этом, называется погрешностью постановки задачи. Часто приходится для решения задачи применять приближенный метод (интеграл заменяют квадратурной суммой, производную заменяют разностью, функцию – многочленом). Погрешность, возникающая при этом, называется погрешностью метода. Часто исходные данные заданы не точно, а приближенно. При выполнении вычислений погрешность исходных данных в некоторой степени переходит в погрешность результата. Такая погрешность называется погрешностью действий. Погрешность, возникающая при округлении бесконечных и конечных десятичных чисел, имеющих большее число десятичных знаков, чем надо в округлении, называется погрешностью округления. Определение. Пусть х – некоторое число, число а называется его приближенным значением, если а в определенном смысле мало отличается от х и заменяет х в вычислениях, . Определение. Погрешностью приближенного значения а числа х называется разность , а модуль этой погрешностью называется абсолютной погрешностью. Если , то а взято с недостатком. Если , то а взято с избытком. Определение. Границей погрешности приближенного значения а числа х называется всякое неотрицательное число , которое не меньше модуля погрешности: . Говорят, что приближение а приближает число х с точностью до , если , , . Пример. Пусть а=0,273 – приближенное значение х с точность до 0,001. Указать границы, в которых заключается х. При округлении чисел считают, что границы погрешности округления равна половине единицы округляемого разряда: , α – порядок округления разряда. Определение. Относительной погрешностью приближенного значения а числа х называется отношение . Пример. Округлить до десятых число 27,52 и найти погрешность и относительную погрешность округления: , , . Также как и абсолютная погрешность относительная погрешность не всегда может быть вычислена и приходится оценивать ее модуль. Модуль относительной погрешности выражается в процентах. Чем меньше модуль относительной погрешности, тем выше качество приближения. Определение. Границей относительной погрешности приближенного значения а числа х называется всякое неотрицательное число , которое не меньше модуля относительной погрешности: . Установим связь между границами погрешностей абсолютной и относительной: - граница относительной погрешности; - граница абсолютной погрешности. . §10. Вспомогательные сведения из функционального анализа. Определение. Множество Х произвольных элементов называется метрическим пространством, если ставится в соответствие число , удовлетворяющее следующим условиям: ; ; – расстояние между x и y. 1-3 – аксиомы метрики. Говорят, что множество элементов - метрическое пространство сходится к , если , . Последовательность точек называется сходящейся в себе (фундаментальной), если . Всякая сходящаяся последовательность является фундаментальной, обратное верно не всегда. Определение. Метрическое пространство, в котором всякая фундаментальная последовательность сходится называется полным. Пример. . Зададим различными способами расстояния: кубическая метрика, m-метрика ; сферическая метрика, метрика ; октаэдрическая, s-метрика . Для всех выполняются аксиомы метрики и в каждой – полное метрическое пространство. Пусть X,Y – метрические пространства. называется оператором, заданным в X со значением в Y. Если X=Y, то – оператор, отображающий Х в себя (преобразование). Если , то – неподвижная точка при отображении . Определение. Говорят, что отображение называется сжимающим (сжатием), если . §11. Решение уравнений с одним неизвестным. Дихотомия. Пусть требуется решить уравнение (1), где – непрерывная функция. Число называется корнем уравнения (1), если . Если функция определена и непрерывна на и на концах отрезка принимает значения разных знаков, то на существует хотя бы один корень. Отделить корень уравнения значит найти такой интервал, внутри которого находится один и только один корень данного уравнения. Для отделения корней можно применить следующий признак: Если на отрезке функция непрерывна и монотонна, и на концах отрезка принимает значения разных знаков, то на данном отрезке существует только один корень уравнения (1). Достаточным условием монотонности функции на отрезке является сохранение знака производной. Отделить корень можно и графически: нарисовать график и указать точки пересечения с осью Ох. Совершенный метод отделения корней – метод Штурма. Дихотомия (метод деления отрезка пополам). Пусть существует хотя бы один корень на ; Рассмотрим и . Из этих двух выберем тот, на концах которого функция принимает значения разных знаков и поделим его пополам и т.д. Если нужно найти корень с точностью до , то мы продолжаем делить отрезок до тех пор, пока длина отрезка не станет меньше , тогда середина последнего отрезка дает значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится всегда для любой непрерывной функции в том числе и недифференцируемой, при этом она устойчива к ошибкам округления. Скорость сходимости метода дихотомии не велика, т.е. за одну итерацию точность увеличивается вдвое. Недостатки: прежде чем применить, необходимо найти отрезок, на концах которого функция принимает значения разных знаков. Если на этом отрезке несколько корней, то неизвестно к какому из них сходится дихотомия. Метод не применим к корням четной кратности. Метод применим к корням нечетной кратности, но хуже устойчив к ошибкам округления. Метод не применим к системам уравнений. §12. Метод простой итерации для решения алгебраических и трансцендентных уравнений. ТЕОРЕМА 1. (Принцип Банаха сжимающихся отображений). Пусть R – полное метрическое пространство. Если сжатие, то для него существует в R единственная неподвижная точка, к которой сходится итерационный процесс. , где - произвольный. План доказательства. – фундаментальная (*) q – коэффициент сжатия . Т.к. R – полное метрическое пространство, то в нем всякая фундаментальная последовательность сходится. – сходится, , причем , т.е. – неподвижная точка. – единственна. ЧТД. - последовательность приближения к решению уравнения Метод – метод простой итерации. Если в (*) зафиксировать, а , то – оценка погрешности, оценка скорости сходимости. со скоростью геометрической прогрессии. – линейная скорость сходимости. Метод простой итерации имеет линейную скорость сходимости. Пусть (2), – вещественная функция. Необходимо привести к виду . , - знакопостоянная непрерывная функция. Условие сходимости для данного метода: ТЕОРЕМА 2. Пусть выполняются условия: Функция – определена и непрерывна на отрезке и на этом отрезке удовлетворяет условию Липшица: ; Для начального приближения выполняется условие ; Числа связаны условием . Тогда уравнение имеет единственное решение в области , к которому сходится итерационный процесс со скоростью сходимости . Теорема доказывается аналогично теореме Банаха с точностью до обозначений. Замечание. Условие Липшица применять трудно, вместо него применяют другое условие: на отрезке . Метод итерация дает бесконечную последовательность приближений, поэтому используют следующие правила остановки: по соседним приближениям задается уровень останова и момент останова n задается формулой по невязке задается уровень и момент останова n итерационной процедуры задается неравенствами Метод простой итерации удобен в использовании, так как он легко программируется на ЭВМ. Недостаток: невысокая скорость сходимости, т.е. линейная. §13. Метод Ньютона. Решение уравнений с одной переменной. Пусть требуется решить уравнение (1), где функция – дважды непрерывно-дифференцируема на ; на и и . Из этих условий вытекает, что на функция имеет только один корень. Прежде, чем использовать итерации, необходимо (1) привести к виду . . Функция непрерывная в окрестности корня уравнения (1). Следовательно, уравнение (1) и уравнение (2) будут иметь один и тот же корень . В качестве выберем , тогда (3) Выберем начальное приближение достаточно близкое к . Остальные приближения получаются по формуле: (4) Метод, определенный (4), называется методом Ньютона. Докажем, что метод Ньютона сходится и получим его оценку погрешности. Если дано, что , где – символ Ландау: если k=1, то скорость сходимости линейная; если k=2, то скорость – квадратичная; если k=3, то скорость – кубическая; если k>1, то сходимость метода сверхлинейная. Докажем, что (4) сходится. Для этого покажем, что отображение – сжатие, где . . При получим . По непрерывности функции на существует такая окрестность точки , что для , , а этом сжатие. Поэтому к отображению можно применить принцип сжатыхотображений. Если выбрать , то будет сходиться к точному решению уравнения (1)., т.е. . Заметим, что метод (4) будет сходиться, если начальное приближение будем выбирать из окрестности , . Докажем, что метод Ньютона сходится. Определим скорость сходимости метода Ньютона. Для этого разложим в ряд Тейлора в точке . . При имеем . Поэтому Выразим (5) Обозначим через , (6) , скорость сходимости метода Ньютона квадратичная, . Потребуем, чтобы начальное условие выбиралось из условия (7) Тогда из (6) получим - оценка погрешности. Метод Ньютона имеет квадратичную скорость сходимости. Это означает, что при переходе от одной итерации к другой количество верных знаков удваивается в последующем приближении. Достоинство: высокая скорость сходимости, легко программируется на ЭВМ. Недостатки: узкая область сходимости. Если будем решать операторное уравнение , то на каждом шаге необходимо находить значение обратного оператора . Геометрический смысл метода Ньютона. П усть требуется решить уравнение и единственный корень этого уравнения находится на . В точке проведем касательную к графику функции , уравнение касательной: . Если , то – первое приближение к уравнения (1) по методу Ньютона. Возьмем и проведем касательную в этой точке. Получим . Если , то – второе приближение к уравнения (1) по методу Ньютона. И так далее. Отсюда метод Ньютона называют методом касательных. §14. Метод хорд. Метод секущих. По прежнему решаем уравнение (1), где , на и . Т.е. на (1) имеет только один корень. Уравнение (1) запишем в виде , где . Возьмем в качестве , где удовлетворяет условию , . Тогда итерационный метод запишется следующим образом: – метод хорд. Докажем, что метод хорд сходится. Для этого необходимо показать, что . Разложим в ряд Тейлора . Рассмотрим при . . Обозначим через Т.е. . . Следовательно, – сжатие и по принципу Банаха метод хорд сходится. Получим оценку погрешности для метода хорд Так как на , то . Обозначим через - оценка погрешности для метода хорд. Сходимость методы хорд – линейная. Достоинство метода хорд – легкость программирования на ЭВМ. – общий вид метода хорд. Общий вид упростится: При условии , то , ; При условии , то , . Метод секущих. Метод секущих имеет вид: . Скорость сходимости – сверхлинейная. . Метод секущих сходится быстрее метода хорд и метода простой итерации. §15. Метод Гаусса решения систем уравнений. Для решения систем уравнений используют методы: точные и приближенные. К точным относятся: метод Гаусса; метод Крамера; метод оптимального исключения; метод квадратного корня. К приближенным методам решения систем уравнений относятся: метод простой итерации; метод Зейделя; метод Ньютона. Метод Гаусса состоит в том, чтобы исходную систему вида Ах=b (1) с произвольной матрицей А свести к системе вида: (2), где - уже треугольная матрица. Процесс сведения системы (1) к системе (2) называется прямым ходом метода Гаусса. А нахождение неизвестных - обратный ход метода Гаусса. При вычислениях по методу Гаусса велика вероятность случайных ошибок. С целью избежать их вводится контрольный столбец: , где Элементы контрольного столбца преобразовываются по тем же формулам, что и элементы матрицы А. Второй шаг контроля состоит в проверке равенства суммы элементов преобразованной строки и контрольного элемента. Эти величины должны совпадать с точностью до 1,2 единиц последнего разряда. Метод Гаусса с выбором главного элемента. Среди уравнений выбирают уравнение, содержащее наибольший по абсолютной величине коэффициент (главный элемент). Затем уравнение делят на этот главный элемент и из остальных уравнений системы исключают неизвестные, определяемые этим главным элементом. Далее, оставляя неизменным выбранное уравнение с главным элементом, из остальных уравнений системы выбирают новый главный элемент. Потом это уравнение с новым главным элементом делят на новый главный элемент и исключает неизвестное или определяемое из остальных уравнений системы. Для удобства главный элемент помещают в левый верхний угол, переставляя строки и столбцы системы уравнений. В результате преобразований приходим к единичной матрице. Здесь переставляются уравнения, что приводит к изменению порядка исключенных неизвестных, и во многих случаях уменьшают погрешности, связанные с округлениями. §16. Метод квадратного корня. Метод квадратного корня – точный метод решения систем уравнений и он применяется для решения систем уравнений, если матрица А – симметричная, т.е. . , где С – верхняя треугольная матрица; – транспонированная, ; D – диагональная, . Подставим матрицу А в систему (1) Ах=b. (2) Тогда (3) Выразим элементы матрицы С через элементы исходной матрицы А. , , (*) (4) Из (4) будем получать выражения через : Пусть , тогда Пусть , тогда Пусть , тогда Из формулы (*) получаем: , Получили формулы: , §2. Оценка погрешностей результатов действий над приближенными значениями чисел. (Строгий учет погрешности) Пусть , где – число с заданными своими приближениями с точностью до : . Обозначим через . , где - граница погрешности суммы приближенного значения . Утверждение 1. Сумма границ погрешностей приближенных слагаемых является границей погрешности их алгебраической суммы. Доказательство: . ЧТД. Утверждение 2. Среди границ относительной погрешности суммы приближенных слагаемых существует такая, которая не превосходит наибольшей из границ относительной погрешности слагаемых: . Утверждение 3. Сумма границ относительных погрешностей сомножителей является границей относительной погрешности их произведения: . Следствие 1. При умножении приближенных значений числа на точный множитель к, граница относительной погрешности не меняется, а граница абсолютной погрешности увеличивается в раз. Следствие 2. Произведение границы относительной погрешности приближенного значения а числа х на является границей относительной погрешности результата возведения числа а в целую положительную степень n: . Следствие 3. Частное границы относительной погрешности приближенного значения а числа х и n является границей относительной погрешности корня n-й степени из а: . Следствие 4. Сумма границ относительных погрешностей приближенных значений делимого и делителя является границей относительной погрешности частного. §3. Приближенные вычисления без учета погрешностей. Правило 1. Для того, чтобы вычислить алгебраическую сумму приближенных слагаемых нужно: среди слагаемых выбрать наименее точное (имеет наименьшее число разрядов после запятой); все остальные слагаемые округлить, сохраняя один запасной разряд, следующий за последним разрядом выделенного слагаемого; сложить полученные после округления числа; округлить полученный результат до предпоследнего разряда. Пример. S=2.737+0.77974+27.1+0.283 2.74+0.78+27.1+0.28 30.90 30.9. Определение 1. Значащими цифрами в десятичной записи числа называется все его цифры кроме нулей, записанных слева от первой цифры не равной 0. 0,00237 – 3 значащие цифры; 0,02000 – 4 значащие цифры. Правило 2. Для того, чтобы вычислить произведение (деление) приближенных чисел нужно: выделить сомножитель, содержащий наименьшее число значащих цифр; округлить остальные сомножители, оставляя на одну значащую цифру больше, чем в выделенном сомножителе; произвести умножение (деление); округлить полученный результат, сохраняя столько значащих цифр, сколько их в выделенном сомножителе. Пример. Р=3,34*0,7*4,748=4,7*3,3*0,7 10,657 1* . Правило 3. При возведении приближенного значения в квадрат или куб, при извлечении квадратного или кубического корня, в результате следует оставлять столько значащих цифр, сколько их имеет основание. Правило 4. Если число является результатом промежуточных действий, то следует сохранить в нем на 1-2 цифры больше, чем указано в правилах 1-3. §4. Связь между числом количества верных цифр и относительной погрешностью. Пусть . Определение. Цифра приближенного значения а называется верной, если модуль его погрешности не превосходит половины единицы этого разряда. . Очевидно, что все цифры, стоящие слева от верной цифры – верные. Пример. Пусть х=27,421, а=27,381, . Выясним, какие цифры верные в приближении а? 4 – , следовательно, 4 – неверная; 8 – , следовательно, 8 – неверная; 3 – , следовательно, 3 – верная. 3,2,7 – верные цифры. Пусть известно количество n верных значащих цифр в приближении а, тогда а запишем: . Так как цифра, стоящая в разряде -(n-1) верна, то погрешность , тогда . В качестве границы относительной погрешности можно взять . Итак, доказана теорема 1. Теорема 1. Если приближение имеет n верных значащих цифр, то число является границей его относительной погрешности. Теорема устанавливает связь между числами верных значений и его относительной погрешностью. Замечание. Пусть приближение имеет n верных значащих цифр и – его первая значащая цифра, тогда число является границей относительной погрешности. Пример. . Итак, граница относительной погрешности приближенного значения зависит от первой значащей цифры , количества верных цифр приближения, но не зависит от порядка приближения. Теорема 2. Если граница относительной погрешности приближения равна , то приближение имеет не менее n значащих цифр. Доказательство. Пусть - первая значащая цифра приближения а и n – порядок, тогда . Из определения следует, что –(m-1) – цифра, записанная в этом разряде верная, цифры, записанные левее тоже верные, то есть m верных цифр. ЧТД. Пример. Если известно, что относительная погрешность приближения , то согласно теореме 2, это приближение имеет ровно 3 верные значащие цифры. , следовательно, по теореме 2, приближение имеет не менее 3-х верных значащих цифр. §5. Прямая задача теории погрешностей (функции от приближенных значений аргументов). Пусть функция определена и непрерывно-дифференцируема по всем переменным в области . Переменные заданы своими приближениями: и точка Известна погрешность элементов . Необходимо оценить погрешность . . Предположим, что малы, поэтому их произведениями, квадратами и более высокими степенями можно пренебречь. Если , то последнюю часть можно поделить на функцию . Пример. Вычислить величину погрешности приближенного значения большего корня уравнения . В приближенной записи используют только верные цифры, ????????????????????, обусловленные погрешностью приближенных значений коэффициентов. , . Теперь обозначим . Рассмотрим . §6. Обратная задача теории погрешностей. Все задачи теории погрешностей делятся на прямые и обратные. Прямая задача: определить погрешность данной функции от приближенных значений аргументов, заданных с известной относительной погрешностью или с заданной точностью. Обратная задача: какими должны быть относительная и абсолютная погрешности, чтобы модуль относительной или абсолютной погрешности заданной функции не превышал заданной величины. Решение обратной задачи. Пусть определена и непрерывно-дифференцируема в области и точка . С какой точностью следует взять приближенные значения для аргументов , чтобы погрешность значения функции не превышала по модулю . – известно, найти . Существуют различные подходы к решению таких задач. Принцип равных влияний заключается в предположении, что погрешности всех аргументов вносят одинаковые доли в погрешности функции, то есть частные дифференциалы равны между собой по модулю: Предполагают, что погрешности всех аргументов равны , тогда . Пример. С какой точностью следует взять дроби, чтобы сумма S могла быть получена с точностью до 0,001? Решение. Обозначим 1-й принцип . Сколько знаков после запятой нужно брать в дробях, чтобы получилась эта погрешность. Дроби необходимо представить в десятичном виде та, чтобы модуль не превосходил 0,00025, т.е. четырьмя десятичными знаками после запятой. §7. Метод границ. Существуют различные способы оценки точности приближенных вычислений: строгий учет погрешностей; вычисления без учета погрешностей; метод границ. Метод границ позволяет установить границы, в которых находится значение, вычисляемое по функции, если известны границы, в которые заключены значения параметров, входящих в формулу. – нижняя граница х; – верхняя граница х х – число. Теорема 1. Сумма верхних границ слагаемых является верхней границей их сумм. Сумма нижних границ слагаемых является нижней границей их суммы. . Пример. Теорема 2. Разность верхней границы уменьшаемого и нижней границы вычитаемого является верхней границей разности. Разность нижних границ уменьшаемого и верхней границы вычитаемого является нижней границей разности. Доказательство. , , сложим данные неравенства и получим результат. ЧТД. Пример. Теорема 3. Пусть нижняя граница сомножителей неотрицательна, то произведение нижних границ сомножителей является нижней границей их произведения, а произведение верхних границ сомножителей является верхней границей их сомножителей. Пример. . Теорема 4. Если и n – целое положительное число, то , . Теорема 5. Если НГ делителя положительна, то частное ВГ делимого и НГ делителя является ВГ частного чисел; частное НГ делимого и ВГ делителя является НГ частного . Доказательство. Перемножим и получим . ЧТД. Пример. Вычислим значение , где . Действие Содержимое НГ ВГ (1) x 2.57 2.58 (2) y 1.45 1.46 (3) z 8.33 8.34 (1)+(2) x+y 4.02 4.04 (1)-(2) x-y 1.11 1.13 9.24 9.43 2.28 2.35 §8. Математические модели и численные методы. Велика роль математики в решении задач реального мира. Физиков математика интересует не сама по себе, а как средство решения физических задач. Один из способов решения задач: эксперимент. Другой способ: математический анализ конструкции или явления, однако такой анализ применяется не к самому явлению, а к его математической модели. Математическая модель физического процесса представляет собой совокупность уравнений, описывающий процесс. Математическая модель должна охватывать важнейшие стороны явления или процесса. Если математическая модель выбрана не точно, то какой бы мы способ решения не применили, результаты могут получиться не достаточно надежными, а иногда и неверными. Поэтому 1-я стадия работы: Постановка задачи. 2-я стадия работы: Математическое исследование. В зависимости от сложности модели применяют различные математические подходы, для наиболее грубых и наименее сложных моделей зачастую удается получить аналитическое решение (в виде формулы). Для наиболее точных и сложных моделей аналитическое решение удается получить крайне редко и тогда применяют численные методы решения, которые как правило требуют расчета на ЭВМ. 3-я стадия работы. Осмысление математического решения и его сопоставление с данными эксперимента. Если решение хорошо согласуется с данными эксперимента, то такую модель можно применять для расчета процессов данного типа (модель выбрана правильно), если же решение плохо согласуется с данными эксперимента, то такую модель необходимо пересмотреть и уточнить. Численные методы являются одним из мощных математических средств решения задач. Есть задачи, где без достаточно сложных численных методов не удалось бы получить ответа. В современной физике таких задач очень много, более того за короткое время нужно провести огромное количество вычислений, иначе нет смысла решать задачу (суточный прогноз погоды должен быть просчитан за несколько часов, а коррекция движения ракеты за несколько минут). Это немыслимо без мощных ЭВМ, выполняющих 1000000 операций в секунду. Современные численные методы и мощные ЭВМ позволили решать задачи, о которых полвека назад человек мог только мечтать. Численные методы делятся на точные и приближенные. Точные методы позволяют за конечное число арифметических действий получить решение задачи. При этом если исходные данные заданы точно и вычисления производились без округления, то получается точное решение задачи. К точным методам относятся: метод Гаусса и его модификации, метод Крамера, метод ортогонализации и т.д. Приближенные методы (итерационные) дают бесконечную последовательность приближений, предел которых, если он существует, является решением задачи. К итерационным методам относятся метод Ньютона и метод простых итераций, метод хорд и метод секущих для решений уравнений. §9. Понятие корректно поставленной и некорректно поставленной задач. При приближенном решении математических или прикладных задач весьма существенным является вопрос о том, корректно ли решаемая задача. Большинство некорректных задач записывается в виде уравнения первого порядка, где по заданному необязательному оператору и по известной правой части требуется найти . - метрические пространства, а в особо оговариваемых случаях – Банаховы или Гильбертовы. Определение. Задача определения решения при заданном называется устойчивой на пространствах и , если (1) Решение устойчиво, если бесконечно малым вариациям правой части соответствуют бесконечно малые вариации х. Определение. Следуя Жаку Адамару задача отыскания уравнения (1) называется корректной (корректно поставленной), если при любой фиксированной правой части решение задачи: существует в Х; единственно в Х; устойчиво в Х. Если же хотя бы одно из условий 1-3 не выполняется, то задача некорректна.