WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
МАТ Е МАТ ИКА МАТ Е МАТ ИКА ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ФУНКЦИОНАЛЬНЫХ УРАВНЕНИЙ В. А. ИЛЬИН Московский государственный университет им. М.В. Ломоносова ВВЕДЕНИЕ Главная цель статьи – познакомить читателя с итерациITERATIVE METHODS онным методом отыскания корней функционального OF SOLVING FUNCTIONAL EQUATIONS уравнения x = F(x), и особенно со случаем, когда оператор, задаваемый функцией F(x), является оператором V. A. IL'IN сжатия. На базе рассмотрения этого метода излагается метод касательных, являющийся одним из наиболее An iterative method of solving the x = F(x) распространенных методов решения функциональноfunctional equation and, based thereon, the го уравнения f(x) = 0.

tangential method of finding the roots of Для чтения статьи не требуется ничего выходящего equation f(x) = 0 are considered.

за рамки программы средней школы. Некоторые предположения из математического анализа, носящие вспоИзложен итерационный метод решения могательный характер и вместе с тем имеющие самостоятельный общематематический интерес, мы приводим с функционального уравнения вида 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).

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

Для доказательства этой теоремы ради определенности рассмотрим случай f '(x0) > 0 (случай f '(x0) < рассматривается совершенно аналогично). Так как производная f '(x0), по определению, равна пределу при x x0 разностного отношения f (x) – f (x0) www.issep.rssi.ru ------------------------------, (1) x – xСОРОСОВСКИЙ ОБРАЗОВАТЕЛЬНЫЙ ЖУРНАЛ, ТОМ 7, №2, Ильин В.А., © МАТ Е МАТ ИКА то в малой окрестности точки x0 разностное отноше- ной на сегменте a x b, то есть для всех x из этого сегние (1) как угодно мало отличается от f '(x0), и так как мента f(x) = f(a) = f(b).

f '(x0) > 0, то в достаточно малой окрестности точки x0 В этом случае производная f '( ) равна нулю в люразностное отношение (1) положительно. Это означает, бой точке сегмента a x b.

что в указанной достаточно малой окрестности этой Пусть теперь f(x) не является постоянной на сегточки f(x) - f(x0) > 0 при x - x0 > 0 и f(x) - f(x0) < 0 при менте a x b. Тогда хотя бы в одной внутренней точx - x0 < 0 или, что то же самое, f(x) > f(x0) при x > x0 и ке x этого сегмента значение f(x) не равно f(a). Пусть f(x) < f(x0) при x < x0.

ради определенности это значение f(x) > f(a). Тогда макТеорема доказана.

симальное значение функции f(x) на сегменте a x b достигается в некоторой внутренней точке этого сег2. Будем говорить, что определенная в некоторой окрестности точки x = x0 функция f(x) имеет в точке x0 мента и функция f(x) имеет в этой точке локальный максимум. По теореме 2 f '( ) = 0.

локальный максимум (соответственно локальный минимум), если существует такая достаточно малая окрест- Теорема доказана.

ность точки x0, в пределах которой значение f(x0) явля4. Теорема 4 (теорема Лагранжа). Если функция ется наибольшим (соответственно наименьшим) среди f(x) непрерывна в каждой точке сегмента a x b и всех значений f(x) этой функции.

имеет производную во всех внутренних точках этого сегТеорема 2. Если функция f(x) имеет производную в мента, то внутри этого сегмента найдется точка, таточке x0 и имеет в этой точке локальный максимум или кая, что справедливо равенство локальный минимум, то обязательно f '(x0) = 0.

f(b) - f(a) = f '( )(b - a), (2) Для доказательства этой теоремы заметим, что функназываемое формулой Лагранжа.

ция f(x), имеющая в точке x0 локальный максимум или Для доказательства этой теоремы рассмотрим на локальный минимум, не может в этой точке x0 ни возсегменте a x b вспомогательную функцию растать, ни убывать. Следовательно, в силу теоремы производная f '(x0) не может быть ни положительна, ни f (b) – f (a)(x F(x) = f (x) – f (a) – ---------------------------- – a) (3) отрицательна, то есть f '(x0) = 0.

b – a Теорема доказана.

и заметим, что для этой функции выполнены на сегЗамечание. Очень далеко идущим обобщением теоменте a x b все условия теоремы 3. Действительно, ремы 2 является принцип максимума Понтрягина, явфункция F(x) непрерывна на сегменте a x b (как ляющийся фундаментальной основой современной теоразность непрерывной функции f(x) и линейной функрии оптимизации.

ции) и имеет во внутренних точках этого сегмента про3. Напомним, что функция f(x) называется непреизводную рывной в данной точке x0, если у этой функции сущестf (b) – f (a).

вует в точке x0 предел lim f (x), равный ее значению F'(x) = f '(x) – ----------------------------x x0 b – a f(x0) в этой точке.

Из равенства (3) очевидно, что F(a) = F(b) = 0. В Теорема 3 (теорема Ролля). Если функция f(x) не- силу теоремы 3 внутри сегмента a x b найдется точпрерывна в каждой точке сегмента a x b и имеет ка, такая, что производную во всех внутренних точках этого сегмента и f (b) – f (a) = 0.

если, кроме того, f(a) = f(b), то внутри этого сегмента F'( ) = f '( ) – ----------------------------b – a найдется точка, производная f '( ) в которой равна нулю.



Теорема доказана.

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

Переходя к доказательству теоремы 3, рассмотрим Введем для этого уравнения понятие итерационной сначала случай, когда функция f(x) является постоян- последовательности.

ИЛЬИН В.А. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ФУНКЦИОНАЛЬНЫХ УРАВНЕНИЙ МАТ Е МАТ ИКА Последовательность чисел x0, x1, …, xn…, коротко функция F(x) имеет производную F '(x) и эта производная обозначаемую символом {xn}, будем называть итераци- всюду на этом сегменте удовлетворяет условию онной, если для любого номера n 1 элемент xn выража|F '(x)| < 1. (5) ется через элемент xn - 1 по рекуррентной формуле xn = Тогда итерационная последовательность {xn}, у ко= F(xn - 1), а в качестве x0 взято любое число из области торой в качестве x0 взята любая точка сегмента [c -, задания функции F(x).

c + ], сходится к корню “c”. Более того, для n-го элеменМы установим, что при определенных условиях та итерационной последовательности xn справедливо неитерационная последовательность {xn} сходится к корравенство ню уравнения (4) и поэтому ее элементы могут быть n взяты за приближенные значения этого корня.

|xn - c|. (6) Теорема 5. Если функция F(x) непрерывна в каждой Замечание 1. Операция, задаваемая функцией F(x), точке сегмента a x b, все элементы итерационной удовлетворяющей неравенству (5), называется сжатием.

последовательности {xn} лежат на этом сегменте и итеЗамечание 2. Неравенство (6) показывает, что итерационная последовательность сходится к некоторому рационная последовательность {xn} сходится к корню c пределу “c”, то “c” является корнем уравнения (4).

со скоростью геометрической прогрессии.

Доказательству теоремы 5 предпошлем следующее Доказательство теоремы 6. В силу теоремы 5 для довспомогательное утверждение.

казательства первого утверждения теоремы 6 о сходиЛемма. Если последовательность {xn} сходится к премости итерационной последовательности {xn} к корню делу “c” и все элементы этой последовательности лежат c уравнения (4) достаточно доказать, что все элементы на сегменте a x b, то и предел “c” лежит на этом xn лежат на сегменте [c -, c + ].

сегменте.

Докажем это методом математической индукции.

Пусть {xn} сходится к пределу c и все элементы xn Так как по условию теоремы x0 принадлежит сегменудовлетворяют неравенству xn b (соответственно xn ту [c -, c + ], то достаточно, предположив, что xn a). Требуется доказать, что и предел c удовлетворяет при n 0 принадлежит этому сегменту, доказать, что и неравенству c b (соответственно c a).

xn + 1 ему принадлежит. Учитывая, что xn + 1 = F(xn), c = Остановимся на случае xn b, ибо случай xn a рас= F(c), мы получим, что сматривается аналогично. Положим yn = xn - b и замеxn + 1 - c = F(xn) - F(c). (7) тим, что последовательность {yn} состоит из неположиТак как функция, имеющая производную в данной тельных чисел и сходится к пределу d = c - b. Достаточно доказать, что этот предел d неположителен. Предполо- точке, является непрерывной в этой точке, то для функции F(x) на сегменте, ограниченном точками c и жение о том, что этот предел положителен, приводит к xn, выполнены все условия теоремы 4 (Лагранжа) и по противоречию с тем, что все yn неположительны, ибо в силу сходимости {yn} к d все элементы yn, начиная с не- этой теореме между c и xn найдется такая точка, что n справедлива формула Лагранжа которого номера, будут как угодно мало отличаться от d и поэтому будут положительны.

F(xn) - F(c) = (xn - c)F '( ). (8) n Лемма доказана.

Из равенств (7) и (8) и условия (5), справедливого Переходя к доказательству теоремы 5, мы теперь в для производной во всех точках сегмента [c -, c + ], силу леммы можем утверждать, что предел c итерационвытекает, что ной последовательности {xn} лежит на сегменте a x b.

|xn + 1 - c| | xn - c|. (9) Отсюда следует, что функция F(x), по условию непрерывная в каждой точке этого сегмента, является непреИз неравенств (9) и из того, что < 1, вытекает, что рывной в точке c. Так как последовательность {xn} схо|xn + 1 - c| < |xn - c|. (10) дится к c, то, по определению непрерывности функции, Неравенство (10) означает, что точка xn + 1 лежит на меньlim F(xn – 1) = F(c).

n шем расстоянии от c, чем точка xn, и так как xn лежит на Переходя теперь к пределу при n в равенстве сегменте [c -, c + ], то и xn + 1 лежит на этом сегменте.

xn = F(xn - 1), мы получим в пределе из этого равенства, Итак, все элементы итерационной последовательчто c = F(c), то есть c является корнем уравнения (4).

ности {xn} лежат на сегменте [c -, c + ], и первая часть Теорема 5 доказана. теоремы 6 доказана.

Теорема 6. Пусть число “c” является корнем урав- Остается для любого номера n доказать неравенстнения (4) и пусть в каждой точке некоторого симмет- во (6). Записывая неравенство (9) для номеров n, равричного относительно “c” сегмента [c -, c + ], где > 0, ных 0, 1, 2, …, n - 1, получим, что СОРОСОВСКИЙ ОБРАЗОВАТЕЛЬНЫЙ ЖУРНАЛ, ТОМ 7, №2, МАТ Е МАТ ИКА n n y |xn - c| |x0 - c|.





y = x Теорема 6 полностью доказана.

Сделаем практические замечания относительно применения только что доказанной теоремы. Предпоx1 = F(x0) ложим, что путем предварительной прикидки мы устаxновили, что интересующий нас корень c уравнения (4) лежит внутри некоторого сегмента [a, b], на котором x2 = F(x1) функция F(x) имеет производную, удовлетворяющую y = F(x) условию (5). Так как сегмент [a, b], вообще говоря, не является симметричным относительно вычисляемого корня c, то естественно возникает вопрос, как выбрать 0 a x0 x2 c x3 x1 b x нулевое приближение x0, чтобы к итерационной последовательности {xn} была применима теорема 6. ЗамеРис. тим, что, где бы внутри сегмента [a, b] ни располагался корень c, хотя бы один из двух симметричных относиМЕТОД КАСАТЕЛЬНЫХ тельно точки c сегментов [a, 2c - a] и [2c - b, b] целиком принадлежит сегменту [a, b]. Поэтому хотя бы одна из Метод касательных является одним из самых эффекдвух точек a и b принадлежит симметричному относитивных приближенных методов вычисления корней тельно c сегменту, всюду на котором справедливо нерауравнения f(x) = 0.

венство (5), то есть хотя бы одну из точек a или b можно Пусть искомый корень c уравнения f(x) = 0 распосогласно теореме 6 выбрать в качестве нулевого приложен на сегменте [a, b]. Перейдем к описанию метода ближения x0. Конкретно за x0 нужно принять ту из токасательных, не выясняя пока условий, при которых чек a или b, для которой приближение x1 = F(x0) не выэтот метод применим. Обратимся к рассмотрению граходит за пределы сегмента [a, b].

фика функции f(x) на сегменте [a, b] (рис. 3). Примем На практике чаще всего встречается случай, когда за нулевое приближение искомого корня некоторое производная F '(x) имеет на сегменте [a, b] определензначение x0 из сегмента [a, b] и обозначим через B0 точный знак. Если этот знак положителен, то из формул ку графика функции с абсциссой x0. Проведем через (7) и (8) вытекает, что итерационная последовательточку B0 касательную к графику функции и возьмем в ность {xn} является монотонной (то есть или не убывает, качестве первого приближения искомого корня абсили не возрастает). Этот случай приводит к так называциссу x1 точки пересечения этой касательной с осью емой ступенчатой диаграмме, изображенной на рис. 1.

Ox. Далее проведем касательную к графику функции Если же производная F '(x) отрицательна на сегменте через точку B1 с абсциссой x1 и возьмем за второе при[a, b], то из тех же формул (7) и (8) вытекает, что два люближение абсциссу x2 точки пересечения этой касабых последовательных элемента xn и xn + 1 лежат по разные тельной с осью Ox. Продолжая этот процесс неогранистороны от c. Этот случай приводит к так называемой ченно, мы построим последовательность x0, x1, …. xn, … спиралеобразной диаграмме, изображенной на рис. 2.

приближенных значений этого корня.

В практических целях полезно получить рекуррентy y y y = x = = x x ную формулу, выражающую xn + 1 через xn. Для этого B y = F(x) Bxx x x1 = F(x0) = = F F ( ( x x ) ) Bx x x2 = F(x1) = = F F ( ( x x ) ) Bc a b x3 x2 x1 x0 a cx3x2 x1 x0 b x A Рис. 1 Рис. ИЛЬИН В.А. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ФУНКЦИОНАЛЬНЫХ УРАВНЕНИЙ МАТ Е МАТ ИКА возьмем уравнение Y - f(xn) = f '(xn)(x - xn) касательной Искомый корень заведомо является положительк графику функции в точке Bn и вычислим абсциссу xn + 1 ным, а в малой окрестности любого положительного точки пересечения этой касательной с осью Ox. При числа выполнены все условия теоремы 7. Далее в силу этом, полагая Y = 0, получим того, что f '(x) = kxk - 1, рекуррентная формула (11) принимает вид f (xn) xn + 1 = xn – --------------. (11) f '(xn) xk – a n xn + 1 = xn – ------------Формула (11) определяет алгоритм метода касаkxk – n тельных.

и после элементарных преобразований приводится к Заметим, что последовательность {xn}, определяемая равенству соотношением (11), совпадает с итерационной последовательностью, определяемой соотношением xn + 1 = F(xn) -----------xn a–xn + 1 = k – 1 + ------------1. (14) для функции F(x), имеющий вид k kxk n f (x)F(x) = x – ------------. (12) f '(x) Любое число a > 0 можно представить в виде a = 2lx, где l – целое число, а x удовлетворяет неравенству Справедливо следующее утверждение.

Теорема 7. Если точка x = c является корнем урав- -- x < 1. Взяв за нулевое приближение x0 число 2[l/k], нения f(x) = 0 и если функция f(x) в достаточно малой окгде символ [l/k] обозначает наибольшее целое число, рестности точки “c” имеет отделенную от нуля (то содержащееся в дроби l/k, и сделав с помощью формуесть удовлетворяющую условию | f '(x)| m > 0) первую лы (14) всего четыре итерации, мы получим:

производную и ограниченную (то есть удовлетворяющую условию | f "(x)| M) вторую производную, то существу2 = 1,414 213 181, ет > 0, такое, что итерационная последовательность (11), в котором за нулевое приближение x0 взята любая 3 = 1,732 049 942, точка сегмента [c -, c + ], сходится со скоростью гео4 = 1,999 999 046, метрической прогрессии к корню x = c уравнения f(x) = 0.

2 = 1,148 697 853, В силу теоремы 6 достаточно доказать, что для функции F(x), определяемой равенством (12), при до2 = 1,071 773 529.

статочно малом > 0 всюду на сегменте [c -, c + ] справедливо неравенство (5). Так как в силу (12) В качестве литературы рекомендуются § 1 главы книги [1] и введение и глава 11 книги [2].

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.