Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений

 

Содержание.

Введение………………………………………………………...2

1. Метод градиента  (метод скорейшего спуска) для  случая системы нелинейных уравнений……………………….……….3

2. Метод скорейшего  спуска для случая системы  линейных уравнений…………………………………………………………..11

3. Свойства  приближений метода скорейшего спуска……17

Заключение……….………….…………………………………25

Список использованной литературы…………….………….26

Приложение 1……………………………………………………27

Приложение 2……………………………………………………28

Приложение 3……………………………………………………32

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Задачи численного решения систем линейных алгебраических уравнений (ЛАУ) и систем нелинейных численных уравнений многочисленны и весьма разнообразны. Это в первую очередь объясняется многообразием матриц систем ЛАУ и просто матриц для которых необходимо проводить вычисления.

В настоящее время не существует методов, которые в одинаковой мере были бы хороши для всех систем ЛАУ. Почти все методы являются ориентированными и учитывают тем или иным образом  специальные свойства матриц систем ЛАУ.

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

 

 

 

 

 

 

 

 

 

 

 

Метод градиента (метод  скорейшего спуска) для случая системы  нелинейных уравнений.

Пусть имеется система нелинейных уравнений:

             (1)

Систему (1) удобнее записать в матричном  виде:

                                    (2)

где - вектор – функция;     - вектор – аргумент.

Предположим, что функции действительны и непрерывно дифференцируемы в их общей области определения. Рассмотрим функцию:

                              (3)

Очевидно, что каждое решение системы (1) обращает в нуль функцию U(x); наоборот, числа x₁, x₂, ..., x_n, для которых функция U(x) равна нулю, являются корнями системы (1).

Будем предполагать, что система (1) имеет лишь изолированное решение, которое представляет собой точку  строгого минимума функции U(x). Таким образом, задача сводится к нахождению минимума функции U(x) в n-мерном пространстве

.

 

Пусть x – вектор-корень системы (1) и x⁽⁰⁾ – его нулевое приближение. Через точку x⁽⁰⁾ проведем поверхность уровня функции U(x). Если точка x⁽⁰⁾ достаточна близка к корню х, то при  наших предположениях поверхность уровня

                              U(x)=U(x⁽⁰⁾)

будет похожа на эллипсоид.

Из точки х⁽⁰⁾ двигаемся по нормали к поверхности U(x)=U(x⁽⁰⁾) до тех пор, пока эта нормаль не коснется в некоторой точке х⁽¹⁾ какой-то другой поверхности уровня.

                            U(x)=U(x⁽¹⁾).

 

 

                                      

                                                  

                                                                      U(x⁽⁰⁾)

                                                     XXXX

                                    M₀

                                      x⁽⁰⁾

 

                                                         0

 

 

Затем,  отправляясь  от точки х⁽¹⁾, снова двигаемся по нормали к поверхности уровня U(x)=U(x⁽¹⁾) до тех пор, пока эта нормаль не коснется в некоторой точке х⁽²⁾ новой поверхности уровня  U(x)=U(x⁽²⁾) и.т.д.

Так как  U(x⁽⁰⁾)>U(x⁽¹⁾)>U(x⁽²⁾)>..., то, двигаясь по такому пути, мы быстро приближаемся к точке с наименьшим значением U (“дно ямы”), которая соответствует искомому корню х системы (1). Обозначим через

                  градиент функции U(x).

( Градиент есть вектор,  приложенный  в точке х, имеющий направление  нормали n к поверхности уровня функции в данной точке в сторону возрастания U, и длину, равную

Справедлива формула

где e_i(i=1,2,…,n)-орты пространства E_n)

Из  векторных треугольников OM₀M₁,OM₁M₂,... заключаем, что      (p=0, 1, 2, ...).

 

 

 

Остается определить множители  для этого рассмотрим скалярную функцию 

 Функция Ф(l) дает изменение уровня функции U вдоль соответствующей нормали к поверхности уровня в точке х^(р).      Множитель l=l_р надо выбрать таким образом, чтобы Ф(l) имела минимум. Беря производную по l и приравнивая ее к нулю, получаем уравнение

.    (4)

Наименьший положительный  корень уравнения (4) и даст нам значение l_р. Уравнение (4), вообще говоря, нужно решать численно. Поэтому укажем метод приближенного нахождения чисел l_р. Будем считать, что l - малая величина, квадратом и высшими степенями которой можно пренебречь. Имеем:

Ф(l)=

Разлагая функции по степеням l с точностью до линейных членов, получим:

      

 

 

 

где

                    

Отсюда

 

Следовательно

             

где

    

-матрица Якоби вектор-функции  f.

Далее, имеем:

               

Отсюда:

               

 

где W¢(x)-транспонированная матрица Якоби.

 

Поэтому окончательно:

                 (5)

 

где для краткости  положено

                            

причем

                 (p=0, 1, 2, ...).   (6)

            Если допустить, что функция f(x) дважды непрерывно дифференцируема в окрестности искомого корня х, то можно получить более точные формулы для поправок

                        ¹

 

Пример 1.

Методом скорейшего спуска вычислим приближенно корни системы

расположенные в окрестности начала координат.

Имеем:

 

                

Выберем начальное приближение:

По вышеприведенным формулам найдем первое приближение:

 

 

Аналогичным образом  находим следующее приближение:          

 

 

 

Отсюда                                   

                                                                

  Следовательно

 

 

 

Ограничимся двумя итерациями (шагами), и оценим невязку:

 

Замечания:

- Как видно из примера,  решение достаточно быстро сходится, невязка быстро убывает. 

          - При решении системы нелинейных  уравнений методом градиента  матрицу Якоби необходимо пересчитывать  на каждом шаге (итерации).

 

 

Метод скорейшего спуска для случая системы линейных уравнений

 

Рассмотрим      систему линейных уравнений

                        (1)

с действительной матрицей А и столбцом свободных членов

                                               

 

Тогда

                  

 

      

Cледовательно

                                  (2)

где  -невязка вектора и

                        (p=0, 1, 2, ...)     (3)

Применение формул (2) и (3) приводит к громоздким вычислениям. Поэтому, на практике часто вместо «скорейшего  спуска» пользуются просто «спуском», добиваясь минимума функции

                     U=(Ax-b,Ax-b).

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

В общей постановке полагают:

                 (p=0, 1, 2, ...),

где у^(р) – произвольный вектор, направленный наружу поверхности уровня U=const, проходящей через точку х ^(р), т.е.

          

 

Имеем

Отсюда

                  

В зависимости от выбора вектора  у^(р) получаются те или иные расчетные схемы. В частности, если матрица А=А¢-положительно определенная то, полагая будем иметь

                       (4)

(p=0, 1, 2, ...), причем

                        

при . ²

Пример

Методом скорейшего спуска решить систему  уравнений

  (4)

Так  как в матрице системы  преобладают диагональные элементы, то в качестве начального вектора х⁽⁰⁾ примем вектор, координаты которого представляют собой округленные значения корней системы:

 

                    

 

Отсюда, например,

                                 

Следовательно,

 

 

 

Далее,

          

 

         

         

 

Применяя  формулу (3), получаем:

 

                           

Отсюда

 

 

причем

                                 

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

 

                        

 

                         ;

 

                           

Заметим, что в данном случае процесс  приближений сходится медленно: после  пятого приближения мы еще далеки от точных корней системы (4):

                                        

 

 

 

Свойства приближении  метода скорейшего спуска.

 

Исследуем свойства последовательности векторов х⁰, х¹, х²… Для этой цели нам потребуются две леммы, которые доказываются ниже.

Леммы доказаны для системы  Ах=f c положительноопределенной симметрической матрицей А.

Тогда вычислительная схема  имеет вид:

                               (5)

 

К системам с нессиметричным матрицам легко перейти после  умножения системы на матрицу  А¢.

               А¢Ах=А¢f

 

При этом в качестве невязки  мы должны взять вектор

                                    .

(Чтобы не путаться  в переобозначениях в дальнейшем  обозначаем вектор невязки, как  и в предыдущем изложении: r_p.)

 

Лемма 1.

Если a_i –некоторые положительные числа, а g_i некоторые числа, удовлетворяющие неравенствам

        

то справедливо неравенство

         (1*)

Доказательство:

Введем обозначение

    и

тогда неравенство (1*) примет вид

(2*)

 

 

отметим, что

  и   

Так как среднее геометрическое меньше среднего арифметического или  равно ему, то будет

(3*)

 

Функция

       

принимает наибольшее значение на отрезке

               

при

        

Это  значение в обоих случаях  равно

          

Значит,