Методы решения нелинейных уравнений.

Лекция 2. Стр. 1 Лекция 2 Методы решения нелинейных уравнений. Методы решения нелинейных уравнений: постановка задач, обусловленность задач, локализация корней, характеристика итерационных методов. Методы бисекций, простых итераций, Ньютона. Методы решения систем нелинейных уравнений (метод простых итераций, метод Ньютона). Задача численного решения нелинейных уравнений, особенно с учетом простоты рассматриваемых в курсе классов функций, может показаться несколько архаичной, учитывая возможности современных компьютеров и современного математического обеспечения. На самом деле это не так. Дело в том, что численное решение нелинейного уравнения f(x) = 0 — одна из немногих задач, которые могут быть достаточно полно исследованы в рамках нашего курса. Задача имеет простую геометрическую интерпретацию, благодаря которой становятся понятными многие сложные проблемы, возникающие при решении широкого круга вычислительных задач. Вспомним классику. Рассмотрим уравнение f(x) = 0. Корнем (решением) уравнения называется значение x , для которого справедливо f ( x)  0 . Будем в дальнейшем полагать, что в окрестности искомого решения x функция достаточно гладкая — непрерывно дифференцируема нужное число раз. ОПР.Корень x называется простым, если f ( x)  0 , но f ' ( x)  0 . ОПР.Корень x называется кратным, а число k — кратностью корня, если f ( x)  0 , f ' ( x)  f ' ' ( x)  ...  f ( k 1) ( x)  0 , но f ( k ) ( x)  0 . Y x3 x1 x2 x4 X x1 , x3 - простые корни, x2 , x4 - кратные. Задача отыскания простых корней проще, чаще встречается, большинство численных методов предназначено для отыскания простых корней. Из классического анализа известно: Теорема 3.1.Если f(x) непрерывна на [a,b], и принимает на его концах значения разных знаков (f(a) f(b)<0), то на [a,b] есть хотя бы один корень уравнения f(x) = 0. Если отрезок [a,b] содержит единственный корень уравнения, то он называется отрезком локализации. Не существует универсальных методов определения отрезка локализации. На практике используются графики, таблицы значений функции с достаточно малым шагом, анализ поведения производной, физические соображения (анализ модели) и т.п. В рамках нашего курса будут рассмотрены задачи, в которых функция задана аналитически и существует простой корень, который можно локализовать графически. На практике чаще всего представляют интерес не все корни уравнения, а некоторые из них (наименьший, наибольший, принадлежащий некоторому промежутку и т.п.). Найти корень аналитически (точно) — записать формулу для вычисления, в большинстве практических задач не удается, да и не очень нужно, т.к. само уравнение в большинстве практических задач не является "точной" моделью процесса, входящие в функцию параметры определяются экспериментально. Следует заметить, что зачастую сама функция не может быть представлена аналитически, а ее значения получаются как результат работы некоего алгоритма (программы). Лекция 2. Стр. 2 Постановка задачи. Найти с погрешностью, не превышающей  , приближенное значение x * корня x уравнения f ( x)  0 , т.е. такое значение x * , для которого справедливо неравенство x *  x   , где f ( x)  0 . Обычно задача отыскания корня уравнения решается в два этапа. 1-й этап — локализация корня (построение отрезка локализации или построение начального приближения коря). Если a, b — отрезок локализации, то его середину можно считать приближенным значением корня, вычисленным с погрешностью, равной половине длины отрезка локализации. Т.е. если a, b — отрезок локализации, то погрешность корня и x *  x  x*  ba 2 ab — приближенное значение корня, x*  x , x *  x — 2   — оценка погрешности вычисленного приближенного зна- чения корня. 2-й этап — итерационное уточнение корней на отрезке локализации. Полагаем начальное (нулевое) приближение корня x ( 0) равным середине или одному из концов отрезка локализации: x ( 0 )  x ( 0 )  a или x ( 0 )  b .   ab , 2 Затем строим последовательность x (k ) приближенных значений корня (последовательные ите-   рации), сходящуюся к точному значению корня. Т.е. при k   , x ( k )  x . При этом f x ( k )  0 ,  поскольку f x  0 и f(x) непрерывна на отрезке локализации. Как только x ( N )  x   , то полагаем x*  x ( N )  x , т.е. x*  x ( N ) — приближенное значение корня, вычисленное с погрешностью  . Итерационные методы отыскания корней уравнения отличаются друг от друга способами построения итерационной последовательности x (k ) . Если для вычисления очередной итерации x n 1   используются только значения x n и f  x n  , то итерационный метод называется одношаговым. В противном случае — многошаговым. Поскольку значение x неизвестно, в каждом итерационном методе используется свой критерий окончания итерационного процесса. Будут рассмотрены: метод бисекций, метод простых итераций, метод Ньютона и некоторые модификации метода Ньютона. Обусловленность задачи вычисления корня нелинейного уравнения. Итак, рассматривается задача вычисления приближенного значения x * корня x уравнения f ( x )  0 , локализованного в достаточно малой окрестности точного значения корня x . Функцию f (x) полагаем достаточно гладкой на промежутке локализации. Следовательно, исходные данные задачи — значения f (x) в рассмотренной окрестности. Будем полагать, что для приближенных (с учетом погрешностей округления) значений f * ( x ) функции f (x) справедливо неравенство f ( x)  f * ( x)   ,    f * — граница абсолютной погрешности вычисления функции. Для непрерывной f (x) существует такая малая окрестность корня x  , x   , в которой спра-  ведливо неравенство f (x )   .  Лекция 2. Стр. 3 В этой окрестности значения f (x) и f * ( x ) неразличимы. Это означает, что невозможно установить в   какой точке окрестности значение f (x) обращается в нуль. Именно поэтому интервал x  , x   называется интервалом неопределенности корня x . Наша задача состоит в оценке ширины этого интервала — в оценке величины  . Пусть x — простой корень уравнения и x  x   , x   : f x  0, f ' x  0 , f (x )   .     По теореме Лагранжа о конечных приращениях f ( x)  f x  f ' xx  x  f ' xx  x .  А поскольку f (x )   , то имеем f ( x)  f ' x   x  x    , x  x  (неравенства приближенf ' ( x) ные). Следовательно, x    1 , т.е.    x x     . f ' ( x) f ' ( x) f ' ( x) 1 — абсолютное число обусловленности задачи вычисления простого f ' ( x) корня нелинейного уравнения f ( x )  0 . Если x * — корень уравнения f * ( x)  0 , а x — корень уравнения f ( x )  0 , то f x *   и Понятно, что величина выполнено неравенство x  x *       f *  сти 2  2   f *  2 1  f * , т.е. длина интервала неопределенноf ' x  1 1  f * и      f *   f * . f ' x  f ' x  Ясно видно, что с уменьшением f ' x  растет число обусловленности, растет  , увеличивается интервал неопределенности. Этот последнее рассуждение становится очевидным, если рассмотреть на графике поведение в окрестности корня быстро и медленно меняющихся функций. Лекция 2. Стр. 4 Обусловленность задачи вычисления кратного корня уравнения. Разложив f (x) в окрестности кратного корня кратности k по формуле Тейлора до членов порядка k, имеем f ( x)  f ( x )  f ( x )( x  x )  f ( x ) f (k ) ( x ) ( x  x ) 2  ...  (x  x)k , 2! k! тогда f (k ) (x) (x  x)k   и k!      f *  k k! (k ) f x  k  f * . Чрезвычайно важно понимать, что    M x , где  M — машинное эпсилон, погрешность представления в компьютере числа x. Важно понимать, что  — наибольшая достижимая точность вычисления корня и бессмысленно уточнять корень после того, как очередное приближение попало в интервал неопределенности. На практике оценить величину  достаточно сложно. Для определения этого момента предназначено правило Гарвика: последовательные итерации выполняются до тех пор, пока они далеки от интервала неопределенности, т.е. пока x ( k )  x ( k 1) x ( k 1) x ( k  2)  q ( k ) остается меньше 1, как только q (k ) становится больше еди- ницы следует прекратить вычисления, исследовать причину увеличения q (k ) и если устранить ее не удается, положить приближенное значение корня равным x ( k 1) ;полученное таким способом решение — наилучшее из возможных. Метод бисекций Пусть требуется найти корень уравнения f ( x )  0 , f (x) непрерывная функция. Предположим, что найден отрезок локализации [a, b] такой, что f ( a )  f (b)  0 . Тогда, согласно теореме Больцано – Коши, внутри [a, b] существует точка x , в которой значение функции равно нулю, f ( x)  0 . Требуется найти приближенное значение x* корня x уравнения f ( x )  0 с погрешностью, не превышающей  . Итерационный метод бисекций состоит в построении последовательности вложенных отрезков, на концах которых функция принимает значения разных знаков: an , bn , a n1 , bn 1   an , bn , f (an )  f (bn )  0 , n = 0, 1, …. Каждый последующий отрезок получается делением пополам предыдущего отрезка. Для того чтобы найти корень с погрешностью  , деление пополам продолжаем до тех пор, пока длина отрезка не станет меньше 2 . Опишем один шаг итераций. Пусть на (n -1)-м шаге найден отрезок a n 1 , bn1   a, b , такой, что f (an1 )  f (bn1 )  0 и bn 1  an 1  2 . an1  bn1 и вычисляем f ( x n 1 ) . Если 2 a  bn1 f ( xn1 )  0 или bn 1  a n 1  2 ,то вычисления заканчиваются и x*  xn1  n 1 — искомое 2 приближенное значение корня. Если же f ( xn1 )  0 , то из двух половин отрезка выбираем ту, на конДелим отрезок его пополам an1 , bn1  точкой xn1  цах которой функция имеет противоположные знаки: если f ( xn1 )  f (a n1 )  0 , то an  an1 , bn  xn1 , если f ( xn1 )  f (a n1 )  0 , то an  xn 1 , bn  bn1 . Лекция 2. Стр. 5 bn1 x n 1 bn1 a n 1 a n 1 x n 1 an  xn 1 , bn  bn1 an  an1 , bn  xn1 Описанный процесс построения вложенных отрезков позволяет найти корень уравнения как предел по- a n  bn , lim a n  lim bn  lim xn  x . n  n  n  2 bn  a n 1 bn 1  a n 1 1    n 1 b  a , метод сходится со скороПоскольку x  x *  x  x n  2 2 2 2 1 стью геометрической прогрессии со знаменателем q  , для достижения заданной погрешности  , 2 b  a ln b  a  ln  1 1 x  x *  x  x n  n 1 b  a   , следует выполнить N  ln  шагов (поln 2  ln 2 2 следовательности середин вложенных отрезков x n  ловинных делений). Понятно, что деления пополам имеет смысл проводить до тех пор, пока значения f (a n ) и f (bn ) "различимы", т.е. пока f (a n )  f (bn )  ( f *) , т.е. нельзя требовать погрешности, превышающей половину длины интервала неопределенности. Метод бисекций обладает высокой надежностью, поскольку гарантирует достижение требуемой точности вычислений (она не должна превышать половины длины интервала неопределенности). Метод допускает простую геометрическую интерпретацию. Метод простых итераций Функция f (x) непрерывна на отрезке локализации [a, b], f ( a )  f (b)  0 ; требуется найти приближенное значение x* единственного на [a, b] корня x уравнения f ( x )  0 с погрешностью, не превышающей  . Преобразуем уравнение f ( x )  0 к виду удобному для итераций x  (x) . Метод простых итераций состоит в построении итерационной последовательности xn  , xn 1  xn  , n = 0, 1, …, lim x n  x , поскольку для непрерывной функции (x ) справедливо n   lim xn  lim xn    lim xn  x   x . n  n  n  Справедливо следующее утверждение. Теорема 3.2. Если функция (x ) определена и дифференцируема на [a, b], все ее значения принадлежат [a, b], и существует такое число q, что ' ( x)  q  1 на [a, b], то при любом начальном приближении x 0 из [a, b] последовательность xn  xn1  , n = 0, 1, …, сходится к единственному на [a, b] корню x уравнения x  (x) , lim xn  lim xn    lim xn  x   x . n  n   n   n При этом x  x n  q x  x 0 и если ' ( x )  0 на [a, b], то x n  x  ' ( x)  0 на [a, b], то x n  x  x n  x n 1 . Доказательство теоремы q x n  x n 1 , а если 1 q Лекция 2. Стр. 6 x  x n  x    x n 1    ' c n 1   x  x n 1  q x  x n 1  q x    x n  2    q   ' c n  2   x  x n  2  q 2 x  x n  2  ...  q n x  x 0 . xn  x   xn1    x    '  n   xn1  x    '  n   xn1  xn    '  n   xn  x  , xn  x   '  n   xn  x   '  n   xn1  xn  , xn  x  1   '  n    '  n   xn1  xn  ,  '  n   xn1  xn  , 1   '  n   '  n  q xn  x   x n 1  x n  x n 1  x n . 1   '  n  1 q x  x  n Величину q в практических задачах оценить не просто. Можно положить q x n  x n 1 . x n 1  x n  2 Опишем один шаг итераций. Пусть на (n -1)-м шаге найдено значение x n 1 . Вычисляем y  xn 1  . Если y  x n 1   , то полагаем x n  y и выполняем очередную итерацию. Если же y  x n 1   , то вычисления заканчиваем, полагая x  x*  y . При этом, если ' ( x )  0 , то погрешность приближенного корня не превышает  , а если ' ( x)  0 , то погрешность приближенного корня не превышает Следовательно, если xn  x  q . 1 q q xn1  xn   , то требуемая точность достигнута. Отсюда — усло1 q вие окончания итерационного процесса: Итерации заканчиваются, когда x n  x n 1    1 q и x  x*  xn . q Следствие 3.2. 1. Если    0 на a, b , то xn  сходится к x , монотонно возрастая в случае a  x0  x , и монотонно убывая в случае x  x0  b 2. Если    0 на a, b , то сходимость xn  к x носит колебательный характер, т.е. при всех n  0 значения x n и x n 1 расположены по разные стороны от x , причем последовательности приближений с четными и нечетными номерами сходятся к x монотонно.(см.рисунок выше) Обусловленность метода простых итераций. Справедлива следующая оценка абсолютного числа обу-  * 1 .Действительно, поскольку  f *   * , то   x *  , т.е. задача плохо 1 q 1 q обусловлена, когда ' x  1 . Из последнего неравенства следует, что для длины интервала неопределен  * ности  справедлива оценка   . 1 q словленности:   Метод простых итераций. Замечание о приведении уравнения к виду, удобному для итераций. Пусть на a, b имеет место неравенство 0  m  f ' ( x)  M (если f ' ( x)  0 , то рассматриваем уравнение  f ( x)  0 ). Положим ( x)  x  f ( x) . Лекция 2. Стр. 7 Тогда, поскольку 1  M  ' ( x)  1  f ' ( x)  1  m , то справедлива оценка  2  max ' ( x)  q()  max1  M , 1  m  и q ()  1 при любом    0,  . [ a ,b ]  M M m M m 2 1  1.  1 ; а при   Если   , то q ( )  — q ( )  mM M m M M Метод допускает простую геометрическую интерпретацию. Метод Ньютона Если известно хорошее начальное приближение x 0 корня x уравнения f(x) = 0, то эффективным методом итерационного уточнения корня является метод Ньютона, который еще называют методом касательных. Метод состоит в построении итерационной последовательности xn1  xn  f ( xn ) , n = 0, 1, 2, …, f ' ( xn ) сходящейся к корню x уравнения f(x) = 0. Справедливо следующее достаточное условие сходимости метода. Пусть f(x) определена и дважды дифференцируема на [a, b], причем f ( a ) f (b)  0 , а производные f ' ( x) и f ' ' ( x ) сохраняют знак на [a, b]. Тогда, исходя из любого начального приближения x 0 , удовлетворяющего условию f ( x0 ) f ' ' ( x0 )  0 , можно построить последовательность xn1  xn  f ( xn ) , n = 0, 1, 2, …, f ' ( xn ) сходящуюся к единственному на [a, b] решению уравнения f ( x )  0 . Для оценки погрешности приближения корня можно воспользоваться неравенством x  xn  M2 2 xn  xn1 , где M 2  max f ' ' ( x) , m1  min f ' ( x) . [ a ,b ] [ a ,b ] 2m1 Значит, если требуется найти корень уравнения с погрешностью, не превышающей  , то итерации прекращаем когда x n  x n 1  2m1  , а приближенное значение корня полагаем равным x n . M2 Приведенная оценка погрешности означает, что метод Ньютона имеет квадратичную сходимость и при хорошем нулевом приближении может сходиться очень быстро. Однако следует понимать, что если вблизи корня значение f ' ( x) становится малым, то сходимость итерационной последовательности замедляется. Поскольку оценка производных функции f(x) часто бывает затруднительной, на практике предпочтительно используют оценку x n  x n 1   . (Соответствующее утверждение доказано в [1], теорема 4.7, стр. 108). Лекция 2. Стр. 8 Опишем один шаг итераций. Пусть на (n -1)-м шаге найдено значение x n 1 . Вычисляем f ( xn1 ) f ( xn1 ) и xn  xn1  . Если f ' ( xn1 ) f ' ( xn1 ) f ( x n 1 ) f ( x n 1 )   , то вычисления закан  , то выполняем очередную итерацию. Если же f ' ( x n 1 ) f ' ( x n 1 ) чиваем, полагая x  x*  xn . При этом, если известны оценки M 2  max f ' ' ( x) , [ a ,b ] m1  min f ' ( x) , то приближенное значение корня на самом деле вычислено с погрешностью, не [ a ,b ] превышающей 2m1 . M2 Для длины интервала неопределенности  справедлива оценка    f * (при условии, что производf ' ( x) ная f ' вычисляется хотя бы с 1-2 верными значащими цифрами; если это не так, особенно, если не удается правильно определить знак f ', метод Ньютона применять не следует из-за медленной сходимости вблизи корня). Итак, метод Ньютона позволяет вычислять решение уравнения с погрешностью, близкой к длине интервала неопределенности,    и    f * ). Заметим, что метод Ньютона хорошо использовать для итераf ' ( x) ционного уточнения, находясь в достаточно малой окрестности корня. Метод допускает простую геометрическую интерпретацию Модификации метода Ньютона Модификации метода Ньютона различаются способом аппроксимации производной f ' ( x) . Упрощенный метод Ньютона: xn  xn1  f ( xn1 ) , f ' ( x0 ) метод можно использовать в случаях, когда производная функции мало меняется вблизи корня; метод обладает линейной сходимостью. Здесь f ' ( xn1 )  f ' ( x0 ) Метод ложного положения: xn  xn1  c  xn1 f ( xn1 ) , f (c)  f ( xn1 ) c — фиксированная точка вблизи простого корня; метод можно использовать в случаях, когда вычисление производной функции затруднительно или нежелательно; метод обладает линейной сходимостью. Здесь f ' ( xn1 )  Метод секущих: xn  xn1  f (c)  f ( xn1 ) c  xn1 xn 2  xn1 f ( xn1 ) , f ( xn 2 )  f ( xn1 ) метод можно использовать в случаях, когда вычисление производной функции затруднительно или нежелательно; метод двухшаговый, обладает сходимостью, более быстрой, чем линейная, сходится с порядком p  p 5 1  1.618 : x n  x  C x0  x . 2 f ( xn 2 )  f ( xn1 ) . xn 2  xn1 f ( xn1 ) Метод Стеффенсена: xn  xn1  f ( xn1 ) , f ( xn1  f ( xn1 ))  f ( xn1 ) Здесь f ' ( xn1 )  Лекция 2. Стр. 9 метод можно использовать в случаях, когда вычисление производной функции затруднительно или нежелательно; метод одношаговый, но, как и метод Ньютона, обладает квадратичной сходимостью. Здесь f ' ( xn1 )  f ( xn1  f ( xn1 ))  f ( xn1 ) . f ( xn1 ) Методы решения систем нелинейных уравнений Рассмотрим систему нелинейных уравнений c m неизвестными:  f1 ( x1 , x 2 ,..., x m )  0,    f ( x , x ,..., x )  0  2 1 2  m , f ( x)  0 , где f ( x)    ...,    f m ( x1 , x 2 ,..., x m )  0  f1   x1     f2   x2  , x   .  ... ...    x  f m   m Задача решения такой системы существенно сложнее задачи отыскания решения нелинейного уравнения. Однако на практике она встречается значительно чаще. Прежде всего, обычно сложно установить имеет ли система решение и сколько у нее решений. Подавляющее большинство методов решения нелинейной системы являются итерационными, они состоят в построении последовательности x (n ) ,   сходящейся к точному решению системы x , Например, x ( n )  x  0 при n   и x  x*  x ( n ) , если x ( n)  x   . Матрицей Якоби рассмотренной системы называют матрицу, обозначаемую J (x ) или f ' (x) , которая определена равенством  f1 (x)   x1  f 2 (x) J (x)  f ' (x)   x 1   ...  f m (x)  x 1  f 1 (x) x 2 f 2 (x) x 2 ... f m (x) x 2 f1 (x)   x m  f 2 (x)  ... x m  . ... ...  f m (x)  ... x1 m  ... Наиболее популярными методами решения нелинейной системы являются метод простых итераций и метод Ньютона. Основные этапы решения. 1. Этап локализации. Для каждого из искомых решений x указывают множество, которое содержит только одно это решение и расположено в достаточно малой его окрестности. Часто в качестве этого множества выступает параллелепипед или шар в n-мерном пространстве. Во многих случаях полное решение задачи локализации невозможно и ее можно считать решенной удовлетворительно, если для x удается найти хорошее начальное приближение. 2. Вычисление решения задачи с заданной погрешностью  с помощью итерационных методов решения систем нелинейных уравнений. Корректность и обусловленность задачи. Будем считать, что система функций f ( x)  0 имеет решение x , причем в некоторой окрестности этого решения матрица Якоби невырождена, что гарантирует , что в указанной окрестности нет других решений системы. В лекции 3 было установлено, что погрешность в вычислении функции f приводит к образованию вокруг корня уравнения f ( x )  0 интервала неопределенности. Аналогично, погрешности в вычислении вектор-функции f приводят к появлению области неопределенности D, содержащей решение системы x такой , что для всех x  D векторное уравнение f ( x)  0 удовлетворяется с точностью до погрешности. Область D может иметь сложную геометрическую структуру. Оценим радиус  этой области. Будем полагать , что для близких к x значений x вычисляемые значения f  (x) удовлетворяет неравенству f (x ) - f  (x)   ( f  ). Тогда  можно приближенно Лекция 2. Стр. 10 (f ( x )) 1 оценить с помощью неравенства    ( f  ). Таким образом, в рассматриваемой задаче роль абсолютного числа обусловленности играет норма матрицы, обратной к матрице Якоби. Метод простых итераций Метод простых итераций решения нелинейных систем состоит в замене исходной системы f ( x)  0 эквивалентной ей системой x  Φ(x) и построении последовательности x ( k 1)  Φ(x ( k ) ) ,сходящейся при k   к точному решению x исходной системы. Нетрудно показать, что xik 1  xi  окрестности точек x и x ( k 1)  x  n k 1 j j 1  xj  xξ  , где ξ — точка, принадлежащая общей j . Т.е. сходимость метода зависит от свойств матрицы Якоби   i J (x)  Φ' (x) . Обычно рассматривают матрицу M  M ij     x j сходимости метода является условие M  1 , например, ( n M )  xi( k )  i , j 1  x n На практике вычисления заканчивают, когда i 1 ( k 1) i 1 2 ij 2   . Поэтому достаточным условием  2  1.   , где  — заданная погреш- ность вычислений. Тогда полагают x  x*  x ( k 1) . Следует, однако, помнить, что при медленной сходимости итерационный процесс может завершиться задолго до достижения корня. С другими критериями окончания итерационного процесса можно ознакомиться отдельно. Здесь они не рассматриваются, поскольку метод простых итераций имеет смысл использовать тогда, когда итерационная последовательность сходится быстро и удовлетворительная погрешность достигается за 2-3 итерации. Метод Ньютона Пусть в окрестности решения системы detf ' (x)  0 (матрица Якоби обратима) и выбрано некоторое нулевое приближение x ( 0) . Последовательные приближения решения в методе Ньютона вычисля-   ются по формуле x( n 1)  x( n)  f ' (x( n) )  f (x( n) ) , n = 0, 1, …, где f ' (x) — матрица, обратная к матрице Якоби. Достаточно часто пользуются упрощенным методом Ньютона, в котором 1 1 f ' (x)1  f ' (x (0) )1 — матрица Якоби и обратная к ней матрица вычисляется один раз, в точке начального приближения x ( 0) . Если detf ' (x)  0 , то в достаточно малой окрестности решения итерационный процесс Ньютона сходится, причем с квадратичной скоростью, т.е. если x ( n 1)  x ( n )   , то x ( n )  x   2   , где x — точное решение системы. Вычисления заканчиваются, когда x ( n 1)  x ( n )   . Иллюстрации Лекция 2. Стр. 11