3. Обобщенный метод Ньютона-Рафсона

При численном анализе эффективный способ нахождения корня одномерного алгебраического уравнения

/ W = О (17.21)

сводится к следующему: сначала делается предположение о первом приближении решения и затем находятся решения в соответствии с последовательностью

( п=1, 2..., (17.22а)

х(п+1) д.(П) .

(х >)

которую можно представить в таком виде:

(17.226)

На графике зависимости / (х) от х итерационный процесс, описываемый с помощью выражения (17.226), можно представить, как. показано на рис. 17,1, откуда видно, что если.

f (х) не имеет особенностей, а df/dx существует и не равна нулю в окрестностях решения, то будет ближе к истинному решению, чем x >. Однако сходимость не обязательно должна иметь место, если выбор осуществлен недостаточно удачно или если f [х) имеет нерегулярный характер в диапазоне значений между x(i> и истинным решением х *. Покажите это.

Метод, выраженный в уравнениях (17.22), был впервые открыт Исааком Ньютоном и обычно известен как метод Ньютона-Рафсона.

Крутизнам f(x >> Крутизиа=~(х>} Крутизна(х >}

Рис. 17.1. Иллюстрация метода Ньютона- Рафсона для Определения корня f (х) = О

Можно прийти К точным достаточным-условиям для сходимости последовательности (17.22) Этот метод можно развить дальше и использовать его применительно к векторному случаю, в котором необходимо найти нуль векторного алгебраического уравнения. Здесь обобщение метода Ньютона- Рафсона приводит к последовательности

dx )х-х(п).

(17.24а)

/(:< )+[() J(-< +>-< >) = 0.

(17.246)

Достаточные условия сходимости в векторном случае представлены также в работе [154]. .

Л. В. Канторович и Г. П. Акилов [101 ] показали, что метод Ньютона- Рафсона вполне можно использовать для решения векторных функциональных уравнений вида

{х) = 0, 17.25)

См. работу [154].

где для наших целей 3 можно рассматривать как ограниченньш оператор, осуществляющий преобразование элементов банахова пространства S6 в другой элемент того же пространства (см. § 11.7).

Для элемента банахова пространства S6, если предел

(17.26)

существует для каждого х в S6, величина 9 (х рассматривается как производная * оператора 0 в Хо- Л. В. Канторович и Г. П. Акилов показали, что если первоначальное приближение х> достаточно близко к решению х*, то функциональное уравнение (17.25) можно решить итерационно с помощью обобщенной последовательности Ньютона-Рафсона

х(п+х) хп) д> (д:(п)) 1 2,... (17.27)

Заметим, что формула (17.27) сразу же указывает [путь решения двухточечной краевой задачи вида

x = f{x,t); x{t,) = x,; x{tz) = Xz, (17.28)

где / имеет непрерывные первые частные производные по X. В банаховом пространстве непрерывной векторной функции времени с нормой, которая определяется также, как в примере 11.5, представим оператор в виде

(17.29)

те 9 I-оператор d/dt; если 52 - оператор, определяемый выражением zix) = f (х, t), то уравнение (17.28) можно написать в виде функционального уравнения 9 (х) = О с соответствующими: краевыми условиями. Оператор d/dt является неограниченным, но формально можно показать, что [105]

2{Х,)={

(17.31)

Ja:=j: \ их \

Следовательно, в соответствии с формулой (17.27) мы имеем итерационную последовательность

Умножив на оператор

dt дх d df

И осуществив перестановку.

лриходим к векторной итерационной последовательности [105]

(л:( )) (л:( +1) - л:( )) + / (л:( ), t)

(17.33)

С краевым условием xit,) = х X (4) = х- Теперь уравнения (17.28)можно .решить с помощью итераций, начав с пробного решения х<> (t), удовлетворяющего указанным краевым условиям.. Так как

{Х( ))

представляет

* В соответствии с определением мы имеем производную Гато или слабую производную оператора Если выражение (17.26) равномерно сходится относительно всех с единич-

ной нормой, то мы имеем производную Фреше, или сильную производную [101].

собой матрицу Якоби для системы (17.28), то мы видим, что уравнение (17.33) является линейным для каждого показателя п и может быть решено для данного краевого условия с помощью метода, описанного в § .12.3.

При использовании необходимых условий, получаемых с помощью вариационного исчисления, принципа максимума или динамического программирования, стандартную задачу оптимального управления, включающую в себя объект п-го порядка, можно свести к задаче с (2п -f 1) дифференциальным уравнениям типа у = f (у, t) * я системе из т алгебраических уравнений вида (z, f)=0 **. Краевые условия даны в двух точках и имеют вид У (i) = 3*1. У id = у2- Таким образом, приведенный выше обобщенный метод Ньютона-Рафсона можно использовать для итерационного решения 2п + m + 1 уравнений. Для (2п + 1) дифференциальных-уравнений используем итерацию вида (17.33). Для т алгебраических уравнений итерационная последовательность выражается с помощью формулы (17.24)

dg (уп, f)

г(У ).05 (17.34)

эту итерацию можно осуществить следующим образом:

1) получим пробное решение у() (t), удовлетворяющее краевым условиям;

2) решение для управляющих воздействий находим из алгебраических уравнений (17.34) путем выражения через первые (2п -f 1) переменных состояния, удовлетворяющих системе из (2п+1) дифференциальных уравнений;

3) (2п + 1) дифференциальных уравнений в форме (17.33) решим методом, приведенным в § 12.3, для получения первых (2п -f 1) составляющих вектора у(2) (fy

4) решения, полученные на третьем этапе, используем для получения последних т составляющих вектора у2) /j

5) повторим этот процесс до тех пор, пока норма разности - у ) не окажется ниже заранее определенного уровня.

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

Имеется сравнительно небольшой практический опыт применения метода Ньютона-Рафсона. Вообще говоря, хотя и существуют теоремы, дающие достаточные условия сходимости, они являются слишком ограничивающими, чтобы быть полезными. Таким образом, приходится обходиться без априор-иоЦ гарантии сходимости. Однако имеющиеся результаты являются, по-видимому, обнадеживающими [105], [135].

Помимо упомянутых здесь методов, можно отметить по меньшей мере еще два менее исчерпывающих метода. Первый из них основан на непосредственном использовании принципов, присущих динамическому программированию (см, § 15.1). Здесь проблемами являются объем памяти и сложность программирования, хотя для частичного решения этих проблем можно ис-

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

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