Документ взят из кэша поисковой машины. Адрес оригинального документа : http://matan.math.msu.su/files/zorich/2%20Uchebnye%20materialy/3%20Chisl%20Metody.pdf Дата изменения: Sat Dec 19 17:26:02 2009 Дата индексирования: Sun Apr 10 21:24:43 2016 Кодировка: Windows-1251

В. А. ЗОРИЧ

НАЧАЛЬНЫЕ СВЕДЕНИЯ О ЧИСЛЕННЫХ МЕТОДАХ РЕШЕНИЯ УРАВНЕНИЙ

(Материал к лекциям по анализу первого семестра)

1


2

Корни уравнений и неподвижные точки отображений

Заметим, что уравнение f (x) = 0, очевидно, равносильно уравнению (x)f (x) = 0, если (x) = 0. Последнее уравнение, в свою очередь, равносильно соотношению x = x - (x)f (x), в котором x можно интерпретировать как неподвижную точку отображения (x) := x - (x)f (x). Таким образом, отыскание корней уравнений равносильно отысканию неподвижных точек соответствующих отображений.
Сжимающие отображения и итерационный процесс

Отображение : X X множества X R в себя будем называть сжимающим отображением, если существует такое число q , 0 q < 1, что для любой пары точек x , x и их образов (x ), (x ) выполняется неравенство |(x ) - (x )| q |x - x |. Ясно, что это определение без изменений распространяется на отображения любых множеств, где определено расстояние d(x , x ) между точками; в нашем случае d(x , x ) = |x - x |. Ясно также, что сжимающее отображение непрерывно и может иметь не более одной неподвижной точки. Пусть : [a, b] [a, b] сжимающее отображение отрезка [a, b] в себя. Покажем, что итерационный процесс xn+1 = (xn ), начинающийся в любой точке x0 этого отрезка приводит к точке x = limn xn , неподвижной для отображения . Заметим сначала, что

|x

n+1

- x n | q |x n - x

n-1

| ... q n |x1 - x0 | ,

поэтому для любых натуральных m, n, таких что m > n, вставляя промежуточные точки и используя неравенство треугольника, получаем оценку qn |xm - xn | |xm - xm-1 | + ... + |x1 - x0 | (q m + ... + q n )|x1 - x0 | < , 1-q из которой следует, что последовательность {xn } фундаментальная (последовательность Коши). Значит по критерию Коши она сходится к некоторой точке x отрезка [a, b]. Эта точка неподвижная точка отображения : [a, b] [a, b], ибо переход к пределу при n в соотношении xn+1 = (xn ), дает равенство x = (x).


3

(Здесь мы воспользовались тем очевидным фактом, что сжимающее отображение непрерывно; кстати, оно даже равномерно непрерывно.) n Переход к пределу при m в соотношении |xm - xn | < 1q q , - дает оценку qn |x - x n | < , 1-q величины уклонения приближения xn от неподвижной точки x отображения .
Метод касательных (метод Ньютона)

Доказывая теорему о том, что непрерывная на отрезке вещественнозначная функция, принимающая на концах отрезка значения разных знаков, имеет на этом отрезке по крайней один нуль (точку, где f (x) = 0), мы предъявили и простейший (но зато универсальный) алгоритм отыскания этой точки (деление отрезка пополам). Скорость сходимости тут порядка 2-n . В случае дифференцируемой выпуклой функции можно пользоваться значительно более эффективным в смысле скорости сходимости методом, предложенным еще Ньютоном. Строим касательную к графику данной функции f в некоторой точке (x0 , f (x0 )), где x0 [a, b]. Находим точку x1 , где эта касательная пересекает ось абсцисс. Повторяя процесс, получаем последовательность {xn } точек, которые быстро сходятся к точке x, в которой f (x) = 0. (Можно проверить, что каждая следующая итерация приводит к удвоению верных значащих цифр приближения к x.) Аналитически, как легко проверить (проверьте!) метод касательных сводится к итерационному процессу

x

n+1

= xn -

f (xn ) . f ( xn )

Например, решение уравнения xm - a = 0, т.е. вычисление этом сводится к итерационному процессу

m a, при

x

n+1

=

1 m

(m - 1)xn + 1 2

a x
m-1 n

.

В частности, для вычисления

a методом касательных получаем xn + a xn .

x

n+1

=


4

Метод Ньютона, как видно из приведенных формул, ищет непоf движные точки отображения (x) = x - f ((x)) . Оно является специx альным случаем рассмотренного в самом первом разделе отображения (x) = x - (x)f (x) и получается из него при (x) = f 1x) . ( Заметим, что в общем случае отображение (x) = x - (x)f (x) f и даже отображение (x) = x - f ((x)) , участвующее в методе касаx тельных, не обязано быть сжимающим. Более того, как показывают простые примеры, в случае общей функции f даже метод касательных не всегда приводит к сходящемуся итерационному процессу. Если же в выражении (x) = x - (x)f (x) функцию (x) удается выбрать так, что на рассматриваемом отрезке | (x)| q < 1, то отображение : [a, b] [a, b], конечно, будет сжимающим. В частности, если в качестве взять постоянную f (1 0 ) , то полуx
(x) x чим (x) = x - ff(x0 ) и (x) = 1 - ff ((x0)) . Если производная функции f непрерывна, по крайней мере в точке x0 , то в некоторой ее x окрестности будем иметь | (x)| = |1 - ff ((x0)) | q < 1. Если отображение переводит эту окрестность в себя (что не всегда так), то стандартный итерационный процесс, индуцированный сжимающим отображением этой окрестности, приведет к единственной в этой окрестности неподвижной точке отображения , в которой исходная функция f обращается в нуль.