Сходимость приближенного метода и оценка погрешности.

Остановимся подробнее на описании тех требований, которые предъявляются к приближенным методам с точки зрения вычислений. Простейшим и основным является требование возможности найти искомую величину с выбранной степенью точности.

Точность вычислений может сильно изменяться от одной задачи к другой. Для некоторых грубых технических расчетов бывает достаточной точность в две-три десятичных значащих цифры. Большая часть инженерных расчетов выполняется на три-четыре десятичных знака. Значительно большей точности часто требуют научные вычисления. Вообще говоря, требования к точности с течением времени растут.

Особенное значение вычислений имеют поэтому такие приближенные методы и процессы, которые позволяют находить результаты со сколь угодно большой степенью точности. Такие методы принято называть сходящимися. Так как они наиболее часто встречаются в вычислительной практике и требования, которые к ним предъявляются, типичны, мы и будем в дальнейшем иметь их в виду.

Пусть х есть точное значение искомой величины. В каждом таком методе может быть построена последовательность приближений к решению х.

После того как указан способ построения приближений, первой задачей теории этого метода будет установление сходимости приближений к решению , и если эта сходимость осуществляется не всегда, то — выяснение тех условий, при которых она имеет место.

Когда сходимость установлена, возникает более трудная и глубокая задача об оценке быстроты сходимости, т. е. оценке того, насколько быстро стремится к решению х при . Всякий сходящийся метод дает принципиальную возможность найти решение со сколь угодно высокой степенью точности, если мы найдем приближение с достаточно большим номером Но, как правило, чем больше тем больше труда нужно затратить на нахождение Поэтому, если медленно стремится к х, то для достижения нужной точности может потребоваться затрата слишком большой вычислительной работы.

В самой математике, и особенно в ее приложениях, известно очень много случаев, когда для нахождения решения х можно указать сходящийся процесс, но оказывается, что он потребовал бы такого количества вычислительного труда, выполнить который невозможно даже при наличии современных быстродействующих машин.

Недостаточно быстрая сходимость есть один из признаков, по которому обычно судят о недостатках метода. Но этот признак, разумеется, не единственный, и при сравнении методов должны быть приняты во внимание еще многие стороны вопроса, в частности удобство проведения вычислений на машинах. Из двух методов иногда предпочтение приходится отдавать методу с несколько более медленной сходимостью, если вычисления по этому методу легче могут быть осуществлены на счетных машинах.

Погрешность, получающаяся при замене х на приближенное значение равна разности Точное значение ее неизвестно, и для того, чтобы судить о скорости сходимости, абсолютную величину разности; оценивают сверху, т. е. строят величину такую, чтобы было

и называют ее оценкой погрешности. Ниже мы приведем примеры оценок По тому, как быстро убывает оценка при возрастании , судят обычно о быстроте сходимости Чтобы оценка отражала действительную степень близости нужно, чтобы мало отличалась от Кроме того, оценка должна быть эффективной» т. е. такой, чтобы ее можно было на самом деле найти, иначе она не сможет быть использована.

Пусть х есть численная переменная величина и ее значение нужно определить из некоторого уравнения. Предположим, что уравнение нами приведено к виду

Применим к решению этого уравнения метод итерации. Его часто называют также методом последовательных приближений. Для пояснения самого метода и связанных с ним оценок остановимся на случае одного численного уравнения. (Этот метод применяют также к системам численных уравнений, к дифференциальным и интегральным уравнениям и во многих других случаях. С применением этого метода к обыкновенным дифференциальным уравнениям читатель встречался в главе V, § 5.)

Будем считать, что мы каким-либо путем нашли приближенное значение для корня уравнения. Если бы было точным решением уравнения (8), то после подстановки его в правую часть уравнения мы должны были бы получить результат, равный Но так как вообще говоря, не совпадает с точным решением, результат подстановки будет отличаться от Обозначим его через

Чтобы установить, в каком случае будет ближе к точному решению, нежели обратимся к геометрическому содержанию нашей задачи Рассмотрим функцию

Возьмем числовую ось и условимся и у изображать точками этой оси. Равенство (9) каждой точкр х ставит в соответствие некоторую точку у той же оси. Его можно рассматривать как правило, дающее точечное преобразование числовой оси на себя.

Зададим на числовой оси отрезок При преобразовании (9) точки перейдут в точки

Отрезок перейдет в отрезок Отношение

будет «коэффициентом растяжения» отрезка при преобразовании. Если то будет происходить сжатие отрезка.

Возвратимся к уравнению (8). Оно говорит о том, что искомая точка х после преобразования должна перейти в себя. Поэтому решение уравнения (8) равносильно нахождению таких точек числовой «оси, которые при преобразовании (9) переходят в себя, т. е. остаются неподвижными.

Возьмем теперь отрезок один конец которого лежит в неподвижной точке х, а другой — в точке При преобразовании перейдет в и отрезок — в отрезок Если функция такова, что при преобразовании (9) происходит сжатие любых отрезков, точка будет, наверное, ближе к корню уравнения (8), чем

Желая получить приближения, сходящиеся к точному решению (8), будем выполнять повторно подстановки в правую часть (8) и построим последовательность чисел

Ниже мы докажем теорему о сходимости последовательных приближений

Предположим, что функция задана на некотором отрезке и равенство (9) дает преобразование на себя, т. е. при всяком х, принадлежащем будет также принадлежать . Будем также считать, что исходное приближение берется на ; все последовательные приближения (10) тогда будут также лежать на отрезке . При этих условиях справедлива следующая теорема. Если имеет производную удовлетворяющую на условию

то справедливы следующие утверждения. У равнение (8) имеет корень х

на отрезке Последовательность (10) сходится к этому корню, и быстрота сходимости характеризуется оценкой

где Уравнение (8) имеет на единственный корень.

Чтобы доказать эти утверждения, оценим разность Если воспользоваться формулой Тейлора [глава II (том 1), § 9, (26)], полагая в ней мы получим

Точка лежит между и заведомо принадлежит отрезку Поэтому

Аналогично

Продолжая такие оценки дальше, найдем, что при всяких значениях выполняется неравенство

Установим теперь сходимость последовательности Для этого рассмотрим вспомогательный ряд

Частичная сумма первых его членов равна

Поэтому и существование конечного предела равносильно сходимости ряда (12). Сравним ряд (12) с рядом

Ввиду оценок (11) члены ряда (12) по абсолютной величине не больше соответствующих членов последнего ряда. Но этот ряд, если в нем исключить первый член является геометрической прогрессией со знаменателем и, так как , ряд сходится. Ряд (12) поэтому будет также сходящимся, и последовательность (10) будет сходиться к некоторому конечному пределу х

Очевидно, х принадлежит отрезку так как ему принадлежат все

Если в равенстве перейти к пределу при то в пределе получится равенство показывающее, что х действительно удовлетворяет уравнению (8). Оценим теперь близость Возьмем и любое следующее приближение

Отсюда, при , ввиду следует

Осталось еще проверить утверждение о единственности. Пусть есть любое другое решение уравнения на Оценим разность

откуда

Так последнее неравенство возможно только при — Значит, решение совпадает с

Доказанная теорема не только указывает условия, достаточные для сходимости метода итерации, но и дает возможность оценить, какое число шагов вычислений нужно проделать, т. е. каким нужно взять чтобы получить нужную точность, если точное решение заменить на Такая оценка эффективна, так как величины входящие в неравенство на самом деле могут быть найдены при помощи исследования функции .

Рассмотрим в качестве примера уравнение встречающееся во многих приложениях. Для определенности рассмотрим случай Пусть нужно найти наименьший положительный корень уравненияж Он должен лежать вблизи точки 1 и быть немного больше 1, в чем легко убедиться, если воспользоваться любыми таблицами или графиком функции

Чтобы обеспечить условие фигурирующее в теореме о сходимости метода итерации, обратим функцию и будем рассматривать уравнение , равносильное заданному.

Приведем результаты вычислений. За исходное приближение было принято значение Следующие приближения вычислялись при

помощи таблицы функции и для них были найдены следующие численные значения

На этом вычисления были прекращены, так как дальнейшие итерации повторили бы все найденные знаки корня

Геометрическая картина приближений к корню изображена на рис. 1. Стремление здесь оказалось настолько быстрым, что уже на чертеже сливается с х.

Рис. 1.

Приведем еще один пример применения метода итерации.

Решим численно интегральное уравнение

Точное его решение есть

Заменим прежде всего интегральное уравнение линейной алгебраической системой. Для этого отрезок интегрирования [0, 1] разделим на четыре равные части точками Значения неизвестной функции у в этих точках обозначим соответственно

Если потребовать, чтобы уравнение удовлетворялось при , и интеграл заменить квадратурной суммой Симпсона для четырех частичных интервалов [глава XII, § 3, формула (6)], то для нахождения получится следующая система уравнений:

Система решалась методом итерации. За исходные приближения для были приняты свободные члены соответствующих уравнении: Найденные значения последующих приближений приведены в табл. 1.

Таблица 1

В конце табл. 1 для сравнения указаны значения точного решения. Дальнейшие приближения не улучшили бы найденные значения Расхождение в последних знаках определяется влиянием погрешности от замены интеграла квадратурной суммой.

Устойчивость метода. Вычисления предъявляют к теории приближенных [методов еще одно общее требование, о котором необходимо упомянуть ввиду его большого значения. Это — требование устойчивости вычислительного процесса. Суть дела здесь заключается в следующем. Каждый приближенный метод приводит к некоторой вычислительной схеме. Часто оказывается, что для получения всех нужных чисел необходимо проделать длительный ряд шагов вычислений по этой схеме. Вычисления на каждом шаге выполняются не совсем точно,

а только на определенное число значащих цифр, и поэтому на каждой шаге мы совершаем некоторую малую погрешность. Все такие погрешности будут сказываться на последующих результатах.

Принятая вычислительная схема может оказаться настолько неудачной, что малые ошибки, допущенные в самом начале расчетов, по мере продвижения в вычислениях будут оказывать на результаты все более и более сильное влияние и в далеких частях вызовут сильные отклонения от точных значений.

Пусть речь идет о численном решении дифференциального уравнения

при начальном условии и (пусть требуется найти значения для равноотстоящих значений

Предположим, что вычисления начаты, доведены до шага и составлена таблица

Мы должны найти теперь . В методе ломаных линий Эйлера приближенно полагают

Здесь находится только по числам которые помещаются в последней строке таблицы. Выскажем пожелание увеличить точность нахождения и воспользуемся для этой цели данными двух последних строк. Тогда может быть построена вычислительная формула

Заметим, что если вычислять абсолютно точно, т. е. с бесконечным числом значащих цифр, то формула (14) будет давать верный результат каждый раз, когда функция у ееть линейный многочлен, тогда как формула (15) будет верпой для всяких многочленов до третьей степени включительно. Казалось бы на первый взгляд, что результаты, полученные при применении формулы (15), должны быть более точными, чем найденные по методу ломаных линий. Однако легко видеть, что

формула (15) непригодна для вычислений, так как ее применение может вызвать быстрый рост погрешности.

Значения производной содержат малый множитель и потому погрешности в этих значениях будут оказывать меньшее влияние, чем погрешности в и Будем для упрощения считать, что значения у находятся точно, и при наблюдении за общей погрешностью не принимать их в расчет. Предположим, что при нахождении мы допустили ошибку а при нахождении ошибку . Тогда, как показывает равенство (15), в мы сделаем ошибку величины ошибка будет —41г и дальше будет быстро возрастать. Формула (15) приводит к вычислительному процессу, неустойчивому относительно погрешностей, и должна быть отброшена.

Приведенный ниже пример достаточно убедительно показывает, к сколь сильному искажению результатов может привести неустойчивость вычислительной схемы. Решалось дифференциальное уравнение при начальном условии Точное решение есть Для численного решения были приняты равноотстоящие значения независимой переменной х с шагом . Приближенные решения вычислялись двумя способами: по методу ломаных линий (14) и по формуле (15). Для сравнения в табл. 2 даны значения точного решения на семь десятичных знаков.

Таблица 2

Приближенные значения решения, найденные по формуле (15), на нескольких первых шагах точнее результатов, полученных методом ломаных линий. Но неустойчивость формулы (15) уже через небольшое число шагов сильно искажает приближенные значения и приводит к числам, весьма сильно отличающимся от истинных значений