Лекции. Источники и классификация погрешностей
 Скачать 3.8 Mb.
|
|
§1. Источники и классификация погрешностей Часто точное численное решение математических задач бывает достаточно сложным, поэтому используют приближённые вычисления. Однако при вычислении вручную некоторые выкладки могут привести к ошибкам. Типы ошибок приближенных вычислений: вычислительные ошибки; ошибки округления; проблемы устойчивости вычислительной схемы. Определение. Численные методы это методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над ними, т.е. к действиям которые выполняет ЭВМ. При численном решении математических и прикладных задач на том или ином этапе возможно появление погрешностей следующих типов: Погрешность задачи. Она связана с приближенным характером исходной содержательной модели (невозможно учесть все факторы в процессе изучения моделируемого явления) и ее математического описания, параметрами которого служат обычно приближенные числа. Погрешность округлений. При выполнении арифметических операций над числами, при вводе и выводе данных производится округление. Погрешность метода. При выборе способа решения поставленной математической задачи выбирают наиболее удобный приближенный способ, который не всегда является точным. Погрешности, соответствующие этим причинам называют:
§2. Погрешность численного решения задачи Введем некоторые переменные. x* точное значение вычисляемого параметра; значение этого параметра соответствующее принятому математическому описанию; решение задачи, получаемое при реализации численного метода в предположении отсутствия округлений; приближенное решение задачи, получаемое при реальных вычислениях; неустранимая погрешность; погрешность метода; вычислительная погрешность; полная погрешность; Чтобы численный метод считался удачно выбранным, необходимо выполнение некоторых условий: А также должно выполняться условие: 0 1 +2 +3. Рассмотрим некоторые возможные подходы к учету погрешностей действий. Пусть А и а два близких числа. А точное значение некоторой величины; a приближенное значение этой величины. его погрешность должна быть в несколько раз меньше неустранимой погрешности (0 < 1); вычислительная погрешность в несколько раз меньше погрешности метода (3 < 2). Определение. Число а называется приближенным значением по недостатку, если оно меньше истинного значения, и по избытку, если больше. Например, число 3,14 является приближенным значением числа по недостатку, а 2,72 – приближенным значением числа е по избытку. Величина a = |А a| называется абсолютной погрешностью приближенного числа a, его относительная погрешность; А = n n1 0, 1 2 … любое число (общий вид); Определение. Значащими цифрами числа a называют все цифры его записи, начиная с первой ненулевой цифры слева. (27,076 пять значащих цифр, 0,000560 три значащих цифры). Определение. Значащую цифру называют верной, если абсолютная погрешность числа не превосходит единицы разряда, соответствующего этой цифре: Пусть a = 27,01768 a = 0,003 а) a = 27,01(7)68; «7»: единица ее разряда 0,001; 0,003 0,001 цифра неверная; б) a = 27,017(6)8; «6»: единица ее разряда 0,0001; 0,003 0,0001 цифра неверная; в) a = 27,0(1)768; «1»: единица ее разряда 0,01; 0,003 0,01 цифра верная; Теорема: Погрешность, возникающая при округлении не превосходит ½ единицы (по абсолютной величине) меньшего из оставленных разрядов. А = 3,1415926 округляют до двух знаков после запятой: а = 3,14. a = |А а| = 0,0015926 (3,1415926 – 3,14 = 0,0015926). Единица меньшего из оставленных разрядов − 0,01 0,0015926 0,005 теорема верна. Повторное округление не рекомендуется, т.к. приводит к увеличению погрешности. Например: Пусть число А = 34,24463, тогда а) а = 34,25; Рассмотрим абсолютные погрешности пунктов а) и b): В случае а) погрешность a = |А а| = |34,24463 – 34,25| = 0,00537, больше погрешности пункта б) a = |А а| = |34,24463 – 34,24| = 0,00463, т.е. 0,00537 0,00463. б) а = 34,24 Следовательно, приближенное значение числа А в пункте b) является более точным. При сложении и вычитании приближенных чисел с различным числом верных значащих цифр после запятой результат округляется по минимальному числу верных цифр после запятой у исходных чисел. При умножении и делении приближенных чисел с различным числом верных значащих цифр производится округление результата с числом значащих цифр, совпадающим с минимальным числом верных значащих цифр у исходных чисел. § 1. Общая постановка задачи Пусть дано уравнение f(x) = 0, где f(x) непрерывная функция. Требуется вычислить действительные корни этого уравнения с заданной точностью. Отделение корней уравнения. Отделить корни значит указать отрезки [ai, bi], на каждом из которых содержится ровно один корень уравнения. а) Обозначим y = f(x) и построим график этой функции, корнями уравнения являются точки пересечения графика функции с осью (ох). y x б) Если уравнение задано в виде g(x) = h(x) (или g(x) h(x) = 0) Введем обозначения y = g(x), y = h(x) и построим эти графики в одной системе координат. Абсциссы точек пересечения и являются корнями уравнения f(x) = 0. y x 0 y = h(x) y = g(x) II. Определение отрезка. На выбранном отрезке [a, b] находится один корень уравнения f(x) = 0. Рассмотрим несколько методов решения уравнений с одной переменной. а) Метод половинного деления (метод вилки) Вилка это любой отрезок, на концах которого функция имеет различные знаки. Пусть функция y = f(x) определена и непрерывна при всех x на отрезке [a,b] и имеет на концах этого отрезка значения разных знаков, т.е. f(а)f(b)0, то существует по крайней мере одна точка С из этого отрезка, значение функции в которой равна нулю. (f(с) = 0) Будем называть отрезок [a, b] промежутком существования корня, а точку с пробной точкой. Обозначим a = a0, b = b0. В результате возможны два случая: 1) f(с0) = 0 с0 точное значение корня; 2) f(с0) 0 ( 0) данный отрезок разбивается на два отрезка [a0, с0] и [с0, b0]. Найдём середину этого отрезка: (Соответственно, если знак функции в т.С совпадает со знаком функции в т. а0, то вместо f(а0) будем использовать f(с0)) Найдем значение функции в этой точке f(с0). Если знак функции в т.С совпадает со знаком функции в т. b0, то в дальнейшем вместо f(b0) будем использовать f(с0). Таким образом из этих двух отрезков выбирают тот, на концах которого функция имеет значения разных знаков. Получается новый отрезок [a1, b1]. Т.е. f(а1) f(b1) 0, и, определив точку с1 [a1, b1] как середину этого отрезка производим те же операции. В результате: Длина отрезка [a1, b1] равна половине длины отрезка [a0, b0]: |[a1, b1]| = ½ |[a0, b0]|; Длина отрезка [a2, b2] равна ¼ длины отрезка [a0, b0]: |[a2, b2]| = ¼ |[a0, b0]| и т.д. Вывод: В качестве приближенного значения корня берем середину отрезка [an, bn] x* точное значение корня cn приближенное значение корня Метод половинного деления позволяет вычислять искомый корень с любой наперед заданной точностью. Он особенно удобен для проведения вычислений на ЭВМ. − число шагов алгоритма − б) метод касательных (метод Ньютона) Пусть действительный корень уравнения f(x) = 0 изолирован на отрезке [a, b], где f(x) – непрерывная функция, а значения f(a) и f(b) на концах отрезка имеют разные знаки и обе производные f ’(x) и f ’’(x) сохраняют знак на всем отрезке [a, b]. Возьмем на [a, b] такое число x0, при котором f(x0) имеет тот же знак, что и f(x0), т.е. такое, что f(x0) f(x0) 0 (в частности за x0 можно принять тот из концов отрезка [a, b], в котором соблюдено это условие). Проведем в точке М0(x0, f(x0)) касательную к кривой f(x). За приближенное значение корня берется абсцисса точки пересечения этой касательной с осью (ох), т.е. точка М1(х1, 0). Рассмотрим случай, когда f(x) и f(x) имеют одинаковые знаки. Пусть у = f(x). Напишем уравнение касательной в точке М0(x0, f(x0)) y = f(x0) + f (x0)(x – x0) – общее уравнение касательной. f (x) 0 f (x) 0 y a b x1 x* A B x f (x) < 0 f (x) < 0 y x a b x1 x* A B Подставим точку М1(x1, 0) в уравнение касательной: 0 = f(x0) + f(x0)(x1 – x0) f(x0)(x1 – x0) = – f(x0) Проведем теперь касательную в точке М1(x1, f(x1)) y = f(x1) + f(x1)(x – x1) и подставим точку М2(х2, 0). 0 = f(x1) + f (x1)(x2 – x1) f (x1)(x2 – x1) = – f(x1) Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень. Вывод: где xn xn+1 Замечание: В случае, когда f (x) и f (x) имеют разные знаки, формулы для нахождения xn+1 имеют тот же вид. (Доказать самостоятельно) Правила выбора исходной точки x0: За исходную точку х0 следует выбирать тот конец отрезка [a, b], в котором знак функции совпадает со знаком f (x). Оценка погрешности (имеет место не только для метода касательных). y = f(x) – дифференцируема на [a, b] x* – точное значение корня уравнения f(x) = 0. x* [a, b], с [a, b], с x* Рассмотрим отрезок с концами x* и с и к этому отрезку применим теорему Лагранжа: Существует такая точка из отрезка с концами x* и с для которой выполняется равенство f(с) – f(x*) = f ’()(с – x*), так как x* – точное значение корня уравнения f(x) = 0, то f(x*) = 0 f(с) = f ()(с – x*). Т.к. точка с не является корнем этого уравнения, то можем записать f(с) 0 f ’() 0. Выразим (с – x*): Отсюда можем написать где – условие окончания вычислений. в) метод хорд Метод заключается в том, что дуга графика функции f(x) = 0 на отрезке [a,b] заменяется стягивающей ее хордой. В качестве приближенного значения корня берется точка пересечения хорды с осью (ох). Пусть функция f(x) определена и непрерывна при всех x [a, b] и на [a, b] меняет знак, т.е. f(а) f(b) 0. Тогда данное уравнение имеет хотя бы один корень. I случай: f (x) и f (x) имеют одинаковые знаки. a b B A f (x) 0 f (x) 0 x1 x2 x* A1 A2 x y Напишем общее уравнение прямой, проходящей через две точки М1(x1, y1) и М2(x2, y2): (М1М2): Используя это уравнение, проведем хорду через точки А(а, f(а)) и B(b, f(b)): возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x1. , отсюда , или Проведем хорду через точки А(х1, f(х1)) и B(b, f(b)): возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x2. отсюда или Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень. Вывод: II случай: f (x) и f (x) имеют разные знаки. a b x* x2 x1 x y B2 B1 B f (x) < 0 f (x) 0 A , у = 0, x = x1 , отсюда , или Проведем хорду через точки А(a, f(a)) и B(x1, f(x1)): , возьмем точку пересечения хорды с осью (ох) с координатами у = 0, x = x2. , отсюда , или Полученная таким образом последовательность x0, x1, x2, … имеет своим пределом искомый корень. Вывод: В качестве начального приближения x0 надо взять тот конец [a, b], в котором знак f(x) и знак f (x) противоположны. Оценка погрешности и условие окончания вычислений такие же, что и в методе касательных. г) комбинированное применение методов хорд и касательных Необходимо найти действительный корень уравнения f(x) = 0, изолированный на отрезке [a, b]. Предполагается, что f(а) и f(b) имеют разные знаки, а каждая из производных сохраняет определенный знак на отрезке изоляции. Возьмем на отрезке [a, b] такую точку x0, что f(x0) и f (x0) имеют одинаковые знаки. Воспользуемся формулами методов хорд и касательных: Величины x11 и x12 принадлежат промежутку изоляции, причем f(x11) и f(x12) имеют разные знаки. Построим новую пару приближений к корню: Точки x21 и x22 на числовой оси расположены между точками x11 и x12, причем f(x21) и f(x22) имеют разные знаки. Вычислим теперь значения: и т.д. Каждая из последовательностей x11, x21, x31, …, xn1, … и x12, x22, x32, …, xn2, … стремится к искомому корню, причем одна из последовательностей монотонно возрастает, а другая монотонно убывает. Пусть – приближенное значение корня, полученное на n-ом шаге методом касательных, а – приближенное значение корня, полученное на n-м шаге методом хорд. Тогда условием окончания вычисления будет: а §1. Постановка задачи Рассмотрим систему из n линейных уравнений с n неизвестными (1) Предположим, что система имеет единственное решение. Найти решение системы А, т.е. с заданной точностью. I. Точные (Прямые) методы Точные (Прямые) методы – это методы, которые приводят к решению за конечное число арифметических операций. а) Формулы Крамера: Запишем систему (1) в матричном виде: АX = В, где – матрица системы; – вектор (столбец) неизвестных; – вектор (столбец) свободных членов. Потребуем от системы выполнение определенных условий: 1. Матрица А должна быть размерностью nn; 2. det A 0. Тогда при небольших n можем использовать формулы Крамера: , (i = 1, 2, 3, … , n) (2) где Ai – матрица nn, получена из матрицы системы А заменой i-го столбца столбцом свободных членов. При использовании формулы Крамера необходимо вычислить (n + 1) определителей. Если определители вычислять разложением по строке (столбцу), то на вычисление определителя n-го порядка будет затрачиваться n! операций умножения. Факториальный рост числа операций с увеличением размерности n называется проклятием размерности (100! 10158), а размерность n = 100 для современных задач не велика. б) Метод Гаусса. Последовательное исключение неизвестных. Выпишем расширенную матрицу. (3) Предположим, что коэффициент a11, называемый ведущим элементом первой строки, не равен нулю. Разделив первую сроку на a11, получим где С помощью первой строки получаем в первом столбце, начиная со второй строки, нули. Для этого, сложим первую строку со следующими строками. Умножив ее на элементы аi1 (i = 2, 3, …, n) с противоположным знаком. где Допустим, что ведущий элемент второй строки, т.е. коэффициент a22(1), тоже отличен от нуля. Тогда, разделив на него вторую сроку, получим С помощью второй строки получаем во втором столбце ниже единицы все нули. Получаем и т.д. В результате получим (4) Переход от расширенной матрицы к матрице (4) называется прямой ход метода Гаусса (получение треугольной матрицы). С помощью последней строки, получаем в последнем столбце все нули выше единицы. Затем с помощью предпоследней строки в предпоследнем столбце получаем нули выше единицы и т.д. Получим Это преобразование называется – обратный ход метода Гаусса (переход от треугольной матрицы к единичной). (5) – решение системы (1). в) Метод Гаусса с выбором главного элемента Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующими недостатками. Если делить на число, близкое к нулю, то получится большая ошибка округления, поэтому если на диагонали матрицы стоят числа близкие к нулю, то приблизительное решение системы получаются с большой погрешностью. Чтобы уменьшить ошибки округления, используют метод Гаусса с выбором главного элемента. Пусть дана система (1). Выпишем расширенную матрицу. В первом столбце среди всех элементов выбираем наибольший по модулю элемент и ту строку, в которой он находится, меняем местами с первой строкой. Затем во втором столбце среди элементов, начиная со второго, выбираем наибольший по модулю элемент и строку, в которой он находится, меняем со второй строкой и т.д. Затем как в методе Гаусса получаем в первом столбце первой строки единицу, а ниже ее нули. Обратный ход тот же, что и в методе Гаусса. Прямые методы приводят к точным решениям, если все вычисления производились без округлений. Невязкой решения называется вектор который равен |AX 0 – B|. , 1 = |a11 x10 + a12 x20 + … + a1n xn0 – b1| По малости невязки решения можно с осторожностью судить о близости найденного приближенного решения x0 и точного решения x*. Замечание. Правило Крамера в ЭВМ не применяется, т.к. оно требует значительно большего числа арифметических действий, чем метод Гаусса. Метод Гаусса используется в ЭВМ при решении систем до порядка 103, а итерационные методы – до порядка 106. n = | an1 x10 + an2 x20 + … + ann xn0 – bn| 2 = |a21 x10 + a22 x20 + … + a2n xn0 – b2| ………………………………………. |