Итерационные методы решения функциональных уравнений

МАТЕМАТИКА ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ФУНКЦИОНАЛЬНЫХ УРАВНЕНИЙ В. А. ИЛЬИН Московский государственный университет им. М.В. Ломоносова

ВВЕДЕНИЕ

ITERATIVE METHODS OF SOLVING FUNCTIONAL EQUATIONS V. A. IL'IN

An iterative method of solving the x = F(x) functional equation and, based thereon, the tangential method of finding the roots of equation f (x) = 0 are considered. Изложен итерационный метод решения функционального уравнения вида x = F(x) и на его базе метод касательных отыскания корней уравнения f(x) = 0.

Главная цель статьи – познакомить читателя с итерационным методом отыскания корней функционального уравнения x = F (x), и особенно со случаем, когда оператор, задаваемый функцией F (x), является оператором сжатия. На базе рассмотрения этого метода излагается метод касательных, являющийся одним из наиболее распространенных методов решения функционального уравнения f (x) = 0. Для чтения статьи не требуется ничего выходящего за рамки программы средней школы. Некоторые предположения из математического анализа, носящие вспомогательный характер и вместе с тем имеющие самостоятельный общематематический интерес, мы приводим с доказательствами, вполне доступными школьникам. ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ Докажем несколько вспомогательных утверждений, имеющих в курсе математического анализа большой самостоятельный интерес. 1. Будем говорить, что определенная в некоторой окрестности точки x = x0 функция f (x) возрастает (соответственно убывает) в точке x0 , если существует такая достаточно малая окрестность точки x0 , в пределах которой f (x) > f (x0) при x > x0 , f (x) < f (x0) при x < x0 (соответственно f (x) < f (x0) при x > x0 , f (x) > f (x0) при x < x0).

© Ильин В.А., 2001

Теорема 1 . Если функция f (x) имеет производную в точке x0 и f '(x0) > 0 (соответственно f '(x0) < 0), то функция f (x) возрастает (соответственно убывает) в точке x0 .

116

Для доказательства этой теоремы ради определенности рассмотрим случай f '(x0) > 0 (случай f '(x0) < 0 рассматривается совершенно аналогично). Так как производная f '(x0), по определению, равна пределу при x x0 разностного отношения

www.issep.rssi.ru

f ( x ) – f ( x0 ) ------------------------------, x – x0

С О Р О С О В С К И Й О Б РА З О В АТ Е Л Ь Н Ы Й Ж У Р Н А Л , Т О М 7 , № 2 , 2 0 0 1

(1)

МАТЕМАТИКА то в малой окрестности точки x0 разностное отношение (1) как угодно мало отличается от f '(x0), и так как f '(x0) > 0, то в достаточно малой окрестности точки x0 разностное отношение (1) положительно. Это означает, что в указанной достаточно малой окрестности этой точки f (x) − f (x0) > 0 при x − x0 > 0 и f (x) − f (x0) < 0 при x − x0 < 0 или, что то же самое, f (x) > f(x0) при x > x0 и f(x) < f(x0) при x < x0 . Теорема доказана. 2. Будем говорить, что определенная в некоторой окрестности точки x = x0 функция f(x) имеет в точке x0 локальный максимум (соответственно локальный минимум), если существует такая достаточно малая окрестность точки x0 , в пределах которой значение f(x0) является наибольшим (соответственно наименьшим) среди всех значений f(x) этой функции. Те ор е ма 2 . Если функция f(x) имеет производную в точке x0 и имеет в этой точке локальный максимум или локальный минимум, то обязательно f '(x0) = 0. Для доказательства этой теоремы заметим, что функция f(x), имеющая в точке x0 локальный максимум или локальный минимум, не может в этой точке x0 ни возрастать, ни убывать. Следовательно, в силу теоремы 1 производная f '(x0) не может быть ни положительна, ни отрицательна, то есть f '(x0) = 0. Теорема доказана. Замечание. Очень далеко идущим обобщением теоремы 2 является принцип максимума Понтрягина, являющийся фундаментальной основой современной теории оптимизации. 3. Напомним, что функция f(x) называется непрерывной в данной точке x0 , если у этой функции существует в точке x0 предел lim f ( x ) , равный ее значению x → x0

f(x0) в этой точке. Те ор е ма 3 (теорема Ролля). Если функция f(x) непрерывна в каждой точке сегмента a # x # b и имеет производную во всех внутренних точках этого сегмента и если, кроме того, f(a) = f(b), то внутри этого сегмента найдется точка ξ, производная f '(ξ) в которой равна нулю. Будем опираться на следующее устанавливаемое в курсе математического анализа утверждение, принадлежащее К.Т.В. Вейерштрассу: если функция f(x) непрерывна в каждой точке сегмента a # x # b, то на этом сегменте найдется точка x0, значение функции f(x0) в которой является максимальным среди всех значений функции f(x) на указанном сегменте, и точка x1 , значение функции f(x1) в которой является минимальным среди значений функции f(x) на указанном сегменте. Переходя к доказательству теоремы 3, рассмотрим сначала случай, когда функция f(x) является постоян-

ной на сегменте a # x # b, то есть для всех x из этого сегмента f(x) = f(a) = f(b). В этом случае производная f '(ξ) равна нулю в любой точке ξ сегмента a # x # b. Пусть теперь f(x) не является постоянной на сегменте a # x # b. Тогда хотя бы в одной внутренней точке x этого сегмента значение f(x) не равно f(a). Пусть ради определенности это значение f(x) > f(a). Тогда максимальное значение функции f(x) на сегменте a # x # b достигается в некоторой внутренней точке ξ этого сегмента и функция f(x) имеет в этой точке ξ локальный максимум. По теореме 2 f '(ξ) = 0. Теорема доказана. 4. Теорема 4 (теорема Лагранжа). Если функция f(x) непрерывна в каждой точке сегмента a # x # b и имеет производную во всех внутренних точках этого сегмента, то внутри этого сегмента найдется точка ξ, такая, что справедливо равенство f(b) − f(a) = f '(ξ)(b − a),

(2)

называемое формулой Лагранжа. Для доказательства этой теоремы рассмотрим на сегменте a # x # b вспомогательную функцию f (b) – f (a) F ( x ) = f ( x ) – f ( a ) – ----------------------------- ( x – a ) b–a

(3)

и заметим, что для этой функции выполнены на сегменте a # x # b все условия теоремы 3. Действительно, функция F(x) непрерывна на сегменте a # x # b (как разность непрерывной функции f(x) и линейной функции) и имеет во внутренних точках этого сегмента производную f (b) – f (a) F' ( x ) = f ' ( x ) – ----------------------------- . b–a Из равенства (3) очевидно, что F(a) = F(b) = 0. В силу теоремы 3 внутри сегмента a # x # b найдется точка ξ, такая, что f (b) – f (a) F' ( ξ ) = f ' ( ξ ) – ----------------------------- = 0. b–a Теорема доказана. ОТЫСКАНИЕ КОРНЕЙ ФУНКЦИОНАЛЬНЫХ УРАВНЕНИЙ МЕТОДОМ ИТЕРАЦИЙ (ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЙ) Этот метод мы применим для отыскания корня функционального уравнения x = F(x).

(4)

Введем для этого уравнения понятие итерационной последовательности.

И Л Ь И Н В . А . И Т Е РА Ц И О Н Н Ы Е М Е Т О Д Ы Р Е Ш Е Н И Я ФУ Н К Ц И О Н А Л Ь Н Ы Х У РА В Н Е Н И Й

117

МАТЕМАТИКА Последовательность чисел x0 , x1 , …, xn …, коротко обозначаемую символом {xn}, будем называть итерационной, если для любого номера n $ 1 элемент xn выражается через элемент xn − 1 по рекуррентной формуле xn = = F(xn − 1), а в качестве x0 взято любое число из области задания функции F(x). Мы установим, что при определенных условиях итерационная последовательность {xn} сходится к корню уравнения (4) и поэтому ее элементы могут быть взяты за приближенные значения этого корня. Те ор е ма 5 . Если функция F(x) непрерывна в каждой точке сегмента a # x # b, все элементы итерационной последовательности {xn} лежат на этом сегменте и итерационная последовательность сходится к некоторому пределу “c”, то “c” является корнем уравнения (4). Доказательству теоремы 5 предпошлем следующее вспомогательное утверждение. Лемма. Если последовательность {xn} сходится к пределу “c” и все элементы этой последовательности лежат на сегменте a # x # b, то и предел “c” лежит на этом сегменте. Пусть {xn} сходится к пределу c и все элементы xn удовлетворяют неравенству xn # b (соответственно xn $ $ a). Требуется доказать, что и предел c удовлетворяет неравенству c # b (соответственно c $ a). Остановимся на случае xn # b, ибо случай xn $ a рассматривается аналогично. Положим yn = xn − b и заметим, что последовательность {yn} состоит из неположительных чисел и сходится к пределу d = c − b. Достаточно доказать, что этот предел d неположителен. Предположение о том, что этот предел положителен, приводит к противоречию с тем, что все yn неположительны, ибо в силу сходимости {yn} к d все элементы yn , начиная с некоторого номера, будут как угодно мало отличаться от d и поэтому будут положительны. Лемма доказана. Переходя к доказательству теоремы 5, мы теперь в силу леммы можем утверждать, что предел c итерационной последовательности {xn} лежит на сегменте a # x # b. Отсюда следует, что функция F(x), по условию непрерывная в каждой точке этого сегмента, является непрерывной в точке c. Так как последовательность {xn} сходится к c, то, по определению непрерывности функции, lim F ( x n – 1 ) = F ( c ). n→∞

Переходя теперь к пределу при n ∞ в равенстве xn = F(xn − 1), мы получим в пределе из этого равенства, что c = F(c), то есть c является корнем уравнения (4). Теорема 5 доказана. Те ор е ма 6 . Пусть число “c” является корнем уравнения (4) и пусть в каждой точке некоторого симметричного относительно “c” сегмента [c − ε, c + ε], где ε > 0,

118

функция F(x) имеет производную F '(x) и эта производная всюду на этом сегменте удовлетворяет условию |F '(x)| # α < 1.

(5)

Тогда итерационная последовательность {xn}, у которой в качестве x0 взята любая точка сегмента [c − ε, c + ε], сходится к корню “c”. Более того, для n-го элемента итерационной последовательности xn справедливо неравенство |xn − c| # εαn.

(6)

Замечание 1. Операция, задаваемая функцией F(x), удовлетворяющей неравенству (5), называется сжатием. Замечание 2. Неравенство (6) показывает, что итерационная последовательность {xn} сходится к корню c со скоростью геометрической прогрессии. Доказательство теоремы 6. В силу теоремы 5 для доказательства первого утверждения теоремы 6 о сходимости итерационной последовательности {xn} к корню c уравнения (4) достаточно доказать, что все элементы xn лежат на сегменте [c − ε, c + ε]. Докажем это методом математической индукции. Так как по условию теоремы x0 принадлежит сегменту [c − ε, c + ε], то достаточно, предположив, что xn при n $ 0 принадлежит этому сегменту, доказать, что и xn + 1 ему принадлежит. Учитывая, что xn + 1 = F(xn), c = = F(c), мы получим, что xn + 1 − c = F(xn) − F(c).

(7)

Так как функция, имеющая производную в данной точке, является непрерывной в этой точке, то для функции F(x) на сегменте, ограниченном точками c и xn , выполнены все условия теоремы 4 (Лагранжа) и по этой теореме между c и xn найдется такая точка ξn , что справедлива формула Лагранжа F(xn) − F(c) = (xn − c)F '(ξn).

(8)

Из равенств (7) и (8) и условия (5), справедливого для производной во всех точках сегмента [c − ε, c + ε], вытекает, что |xn + 1 − c| # α|xn − c|.

(9)

Из неравенств (9) и из того, что α < 1, вытекает, что |xn + 1 − c| < |xn − c|.

(10)

Неравенство (10) означает, что точка xn + 1 лежит на меньшем расстоянии от c, чем точка xn , и так как xn лежит на сегменте [c − ε, c + ε], то и xn + 1 лежит на этом сегменте. Итак, все элементы итерационной последовательности {xn} лежат на сегменте [c − ε, c + ε], и первая часть теоремы 6 доказана. Остается для любого номера n доказать неравенство (6). Записывая неравенство (9) для номеров n, равных 0, 1, 2, …, n − 1, получим, что

С О Р О С О В С К И Й О Б РА З О В АТ Е Л Ь Н Ы Й Ж У Р Н А Л , Т О М 7 , № 2 , 2 0 0 1

МАТЕМАТИКА |xn − c| # αn |x0 − c| # εαn.

y

Теорема 6 полностью доказана. Сделаем практические замечания относительно применения только что доказанной теоремы. Предположим, что путем предварительной прикидки мы установили, что интересующий нас корень c уравнения (4) лежит внутри некоторого сегмента [a, b], на котором функция F(x) имеет производную, удовлетворяющую условию (5). Так как сегмент [a, b], вообще говоря, не является симметричным относительно вычисляемого корня c, то естественно возникает вопрос, как выбрать нулевое приближение x0 , чтобы к итерационной последовательности {xn} была применима теорема 6. Заметим, что, где бы внутри сегмента [a, b] ни располагался корень c, хотя бы один из двух симметричных относительно точки c сегментов [a, 2c − a] и [2c − b, b] целиком принадлежит сегменту [a, b]. Поэтому хотя бы одна из двух точек a и b принадлежит симметричному относительно c сегменту, всюду на котором справедливо неравенство (5), то есть хотя бы одну из точек a или b можно согласно теореме 6 выбрать в качестве нулевого приближения x0 . Конкретно за x0 нужно принять ту из точек a или b, для которой приближение x1 = F(x0) не выходит за пределы сегмента [a, b]. На практике чаще всего встречается случай, когда производная F '(x) имеет на сегменте [a, b] определенный знак. Если этот знак положителен, то из формул (7) и (8) вытекает, что итерационная последовательность {xn} является монотонной (то есть или не убывает, или не возрастает). Этот случай приводит к так называемой ступенчатой диаграмме, изображенной на рис. 1. Если же производная F '(x) отрицательна на сегменте [a, b], то из тех же формул (7) и (8) вытекает, что два любых последовательных элемента xn и xn + 1 лежат по разные стороны от c. Этот случай приводит к так называемой спиралеобразной диаграмме, изображенной на рис. 2. y

y=x

x1 = F(x0)

x1

x2 = F(x1) y = F(x)

0

a x0

x2 c x3 x1

b

Рис. 2

МЕТОД КАСАТЕЛЬНЫХ Метод касательных является одним из самых эффективных приближенных методов вычисления корней уравнения f(x) = 0. Пусть искомый корень c уравнения f(x) = 0 расположен на сегменте [a, b]. Перейдем к описанию метода касательных, не выясняя пока условий, при которых этот метод применим. Обратимся к рассмотрению графика функции f(x) на сегменте [a, b] (рис. 3). Примем за нулевое приближение искомого корня некоторое значение x0 из сегмента [a, b] и обозначим через B0 точку графика функции с абсциссой x0 . Проведем через точку B0 касательную к графику функции и возьмем в качестве первого приближения искомого корня абсциссу x1 точки пересечения этой касательной с осью Ox. Далее проведем касательную к графику функции через точку B1 с абсциссой x1 и возьмем за второе приближение абсциссу x2 точки пересечения этой касательной с осью Ox. Продолжая этот процесс неограниченно, мы построим последовательность x0 , x1 , …. xn , … приближенных значений этого корня. В практических целях полезно получить рекуррентную формулу, выражающую xn + 1 через xn . Для этого

y=x

B B0

y = F(x) x1

x

x1 = F(x0) B1

x2 = F(x1) B2 a 0

a

c x3 x2

x1 Рис. 1

x0

b

x

c x3 x2

x1

x0

b

A Рис. 3

И Л Ь И Н В . А . И Т Е РА Ц И О Н Н Ы Е М Е Т О Д Ы Р Е Ш Е Н И Я ФУ Н К Ц И О Н А Л Ь Н Ы Х У РА В Н Е Н И Й

119

МАТЕМАТИКА возьмем уравнение Y − f(xn) = f '(xn)(x − xn) касательной к графику функции в точке Bn и вычислим абсциссу xn + 1 точки пересечения этой касательной с осью Ox. При этом, полагая Y = 0, получим f ( xn ) -. x n + 1 = x n – -------------f ' ( xn )

(11)

Формула (11) определяет алгоритм метода касательных. Заметим, что последовательность {xn}, определяемая соотношением (11), совпадает с итерационной последовательностью, определяемой соотношением xn + 1 = F(xn) для функции F(x), имеющий вид f ( x) F ( x ) = x – ------------- . f '( x )

(12)

Справедливо следующее утверждение. Те ор е ма 7 . Если точка x = c является корнем уравнения f(x) = 0 и если функция f(x) в достаточно малой окрестности точки “c” имеет отделенную от нуля (то есть удовлетворяющую условию | f '(x)| $ m > 0) первую производную и ограниченную (то есть удовлетворяющую условию | f "(x)| # M) вторую производную, то существует ε > 0, такое, что итерационная последовательность (11), в котором за нулевое приближение x0 взята любая точка сегмента [c − ε, c + ε], сходится со скоростью геометрической прогрессии к корню x = c уравнения f(x) = 0. В силу теоремы 6 достаточно доказать, что для функции F(x), определяемой равенством (12), при достаточно малом ε > 0 всюду на сегменте [c − ε, c + ε] справедливо неравенство (5). Так как в силу (12) [ f '( x )] – f ( x ) f "( x ) f ( x ) f "( x ) F' ( x ) = 1 – --------------------------------------------------= -------------------------, 2 2 [ f '( x )] [ f '( x )] 2

и после элементарных преобразований приводится к равенству a k–1 -. x n + 1 = ----------- x n + -----------k–1 k k xn

(14)

Любое число a > 0 можно представить в виде a = 2lx, где l – целое число, а x удовлетворяет неравенству 1 --- # x < 1. Взяв за нулевое приближение x0 число 2[l/k], 2 где символ [l/k] обозначает наибольшее целое число, содержащееся в дроби l/k, и сделав с помощью формулы (14) всего четыре итерации, мы получим: 2

2 = 1,414 213 181,

2

3 = 1,732 049 942,

2

4 = 1,999 999 046,

5

2 = 1,148 697 853,

10

2 = 1,071 773 529.

В качестве литературы рекомендуются § 1 главы 12 книги [1] и введение и глава 11 книги [2].

1. Ильин В.А., Позняк Э.Г. Основы математического анализа. М.: Наука, 1998. Т. 1. 616 с.

(13)

Далее так как f(c) = 0 и функция f(x) непрерывна в точке c, то можно фиксировать ε > 0 настолько малым, что при c − ε # x # c + ε функция f(x) будет удовлетво2

m рять неравенству f ( x ) # --------. Из последнего неравен2M ства и (13) следует, что при c − ε # x # c + ε 1 F' ( x ) # --- < 1. 2 Теорема 7 доказана. В заключение применим метод касательных для приближенного вычисления корня целой степени k из числа a > 0. Заметим, что вычисляемый корень совпадает с корнем функции f(x) = xk − a.

120

k

xn – a x n + 1 = x n – ------------k–1 k xn

ЛИТЕРАТУРА

то всюду в достаточно малой окрестности точки c f ( x) M -. F' ( x ) # ------------------2 m

Искомый корень заведомо является положительным, а в малой окрестности любого положительного числа выполнены все условия теоремы 7. Далее в силу того, что f '(x) = kxk − 1, рекуррентная формула (11) принимает вид

2. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ I: (Начальный курс). М.: Изд-во МГУ, 1985. 660 с.

Рецензент статьи В.Б. Колмановский *** Владимир Александрович Ильин, доктор физико-математических наук, профессор, зав. кафедрой общей математики ВМК МГУ, главный научный сотрудник Математического института им. В.А. Стеклова РАН, лауреат Государственной премии СССР, действительный член РАН. Автор более 250 научных публикаций по теории функций, теории дифференциальных уравнений и математической физике, университетских учебников по математическому анализу, аналитической геометрии и линейной алгебре и монографии по спектральной теории дифференциальных операторов.

С О Р О С О В С К И Й О Б РА З О В АТ Е Л Ь Н Ы Й Ж У Р Н А Л , Т О М 7 , № 2 , 2 0 0 1