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

   (4*)

при всех i=1, 2, ... n.

 

Теперь из (3*) в силу (4*) получим

Лемма доказана.

 

Введем в рассмотрение понятие  функции ошибки, определив ее формулой

G(x)=(Ae,e)  (5*)

Где e=х^*-х – вектор ошибки, х^*-точное решение системы Ах=f.

Имеет место 

Лемма 2.

Последовательность значений функции  ошибки G(x⁽⁰⁾), G(x⁽¹⁾),..., G(x^(p)). Где х^(р) определяются формулами (5*)  , стремится к 0 при р стремящемся к бесконечности.

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

В силу формул (5) имеем

   

значит,

  (6*)

где

Оценим снизу величину q_p.

Пусть

            

-собственные значения  матрицы А, и u_1, u_2, ..., u_n –принадлежащие им собственные векторы, ортогональные друг к другу и нормированные так, что (u_i,u_i)=1 при i=1, 2, ..., n.

Все l_i >0 , т.к. А - положительно определенная матрица.

Пусть

Разложим вектор r_p по собственным векторам матрицы А:

r_p=c₁u₁+c₂u₂+...+c_nu_n       (7*)

так как под r_p мы понимаем ненулевой вектор невязок системы, то в разложении (7*) не все с равны 0. имеем

 

 

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

                         

Теперь для q_p получим

                        

В силу формулы (1*) отсюда следует

                              

Значит

                       

Далее получим

                              

 

 

или

                 (8*)

Коэффициент <1, поэтому из (8*) следует, что

  при   .

Лемма доказана.

 

 

Теорема

Последовательные приближения  х⁰, х¹, х²…, построенные по методу скорейшего спуска, сходятся к решению системы Ax=f со скоростью геометрической прогрессии.

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

Из Леммы 2 следует, что 

  при  

А это означает, что

 при   ,так как матрица А – положительноопределенная. Определим теперь скорость сходимости. Имеем

    (9*)

где  e^(p) =x^(*)-x^(p).

Из (8*) и (9*) следует оценка

 

 Означающая, что  стремится к нулю со скоростью геометрической прогрессии. Теорема доказана.³

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1. Демидович Борис Павлович, Марон Исаак Абрамович  “Основы вычислительной математики” – М.: Наука, 1966 г. -  664 с.
2. Крылов Владимир Иванович, Бобков Владимир Васильевич, Монастырный Петр Ильич “Начала теории вычислительных методов. Линейная алгебра и нелинейные уравнения.” – Минск: Наука и техника, 1985г.-280с.

3.Симонович Сергей  Виталиевич, Евсеев Георгий Александрович,  “Занимательное программирование  С++” – М.:АСТ Пресс книга, 2001г.-366с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1.

Описание программы.

Программа написана на языке  С++ и скомпилирована в среде Turbo C++ 3.0 для DOS.

Ввод данных осуществляется из файла. Результаты вычислений выводятся  на экран

и в файл. При написании  программы использован объектно-ориентированный  подход (класс „Матрица”).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 2.

Листинг программы.

******************************************************************

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

******************************************************************

#include <math.h>

#include <conio.h>

#include "matrix6.cpp"

double norma(TMatrix<double> &x)

{

   double res=0;

   int m=x.getSizeRow(), n=x.getSizeCol();

 

   for(int i=1; i<=m; i++)

   {

      for(int j=1; j<=n; j++)

      {

res+=x(i,j)*x(i,j);

      }

   }

 

   return sqrt(res);

}

 

 

//решение СЛАУ методом  наискорейшего спуска

TMatrix<double> linearSolveFastDescent(TMatrix<double> &a,//матрица коэфф.

       TMatrix<double> &b,//правая часть

       double sigma,   //погрешность

       long max_step) //максю кол-во шагов

{

  int n=a.getSizeRow();

   TMatrix<double> x(b), a_tr(a.getTranspose()), r(n,1), s(n,1);

 

   for(long k=0; k<max_step; k++)

   {

      r=b-a*x;

      s=a_tr*r;

      x+=(r%r)/(s%s)*s;

 

      if(norma(r)<sigma)

      {

break;

      }

   }

 

   cout<<"число шагов: "<<k<<endl;

 

   if(k==max_step)

   {

      cout<<"заданная точность не достигнута "<<endl;

   }

 

   return x;

}

 

 

void main(void)

{

  char ch;

  TMatrix<double> a_b;

  double sigma=.0000001;

  long max_step=10000;

 

  cout.setf(ios::showpoint);

 

  for(;;)

  {

     clrscr();

     cout<<"Решение СЛАУ"<<endl

<<"Метод скорейшего  спуска "<<endl<<endl

<<"1   - ввести данные  из файла"<<endl

<<"2   - ввести погрешность<<endl

<<"3   - ввести максимальное  кол-во шагов<<endl

<<"4   - решить СЛАУ"<<endl<<endl

<<"Esc - выход"<<endl<<endl<<endl;

 

     do

     {

ch=getch();

     }

     while(ch!='1' && ch!='2' && ch!='3' && ch!='4' && ch!=27);

 

     switch(ch)

     {

case '1':

{

    clrscr();

    char str[20];

    cout<<"введите имя файла:"<<endl;

    cin>>str;

    ifstream in_file(str);

    if(in_file)

    {

       int n;

       in_file>>n;

       a_b.setSize(n,n+1);

       a_b.readArray(in_file);

       a_b.writeArray(cout);

    }

    else

    {

       cout<< не могу открыть файл\"”<<str<<"\""<<endl;

    }

    getch();

    break;

}

case '2':

{

    clrscr();

    cout<<"введите погрешность"<<sigma<<"): ";

    cin>>sigma;

    break;

}

case '3':

{

    clrscr();

    cout<<"введите максимальное количество шагов"<<max_step<<"): ";

    cin>>max_step;

    break;

}

case '4':

{

    TMatrix<double> x;

    clrscr();

    cout<<"Решение СЛАУ“"<<endl;

    cout<<"Расширенная матрица системы"<<endl;

    a_b.writeArray(cout);

    cout<<"Погрешность: "<<sigma<<endl;

    cout<<"Максимальное кол-во шагов: "<<max_step<<endl;

 

    int n=a_b.getSizeRow();

    TMatrix<double> a(a_b.getPart(1,1,n,n)), b(a_b.getCol(n+1));

    x=linearSolveFastDescent(a,b,sigma,max_step);

 

    cout<<"решение: "<<endl;

    x.writeArray(cout);

 

    ofstream out_file("result.txt");

    if(out_file)

    {

       out_file<<"Решение СЛАУ“"<<endl;

       out_file<<"Расширенная матрица системы:"<<endl;

       a_b.writeArray(out_file);

       out_file<<"Погрешность: "<<sigma<<endl;

       out_file<<"Максимальное количество шагов: "<<max_step<<endl;

       out_file<<"Решение: "<<endl;

       x.writeArray(out_file);

    }

    else

    {

       cout<<"не могу создать файл\"result.txt\""<<endl;

    }

 

    getch();

    break;

}

case 27:

{

   return;

}

     }  }

}

        

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 3.

          **************************************************

Шаблон класса "Матрица"   

****************************************************/

#ifndef            MATRIX6_CPP

#define            MATRIX6_CPP

#include           <assert.h>

#include           <iostream.h>

template<class TYPE>

class TMatrix

{

   friend TMatrix  operator+    (TYPE, TMatrix &); //сложение со скаляром

   friend TMatrix  operator-    (TYPE, TMatrix &); //вычитание со скаляром

   friend TMatrix  operator*    (TYPE, TMatrix &); //умножение на скаляр

   friend istream& operator>>   (istream &, TMatrix &); //ввод матрицы

   friend ostream& operator<<   (ostream &, TMatrix &); //вывод матрицы

public:

   TMatrix                      ();                //конструктор по умолчанию

   TMatrix                      (TMatrix &);       //конструктор  копирования

   TMatrix                      (int, int);        //конструктор  с заданием

   //размера

   ~TMatrix                     ();                //деструктор

   void            init         (TYPE c);          //инициализация числом

   void            initStat     (TYPE *p, int, int);//инициализ. статич.

    //массивом

   void            initDynam    (TYPE **p, int, int);//инициализ. динамич.

   //массивом

   void            setSize      (int, int);        //установка размера

   int             getSizeRow   ();                //кол-во строк

   int             getSizeCol   ();                //кол-во столбцов

   TYPE &          operator()   (int, int);        //элемент матрицы

   TYPE &          operator[]   (int);             //элемент

   //матрицы-вектора

   TMatrix &       operator=    (TMatrix &);       //присваивание

   TMatrix         getRow       (int);             //строка

   TMatrix         getCol       (int);             //столбец

   void            setRow       (int, TMatrix &);  //задать строку

   void            setCol       (int, TMatrix &);  //задать столбец

   TMatrix         getPart      (int, int, int, int); //получить часть

   void            setPart      (int, int, TMatrix &); //задать часть

   void            swapRow      (int, int);        //обмен строк

   void            swapCol      (int, int);        //обмен столбцов

   TMatrix         operator+    (TMatrix &);       //сложение матриц

   TMatrix         operator-    (TMatrix &);       //вычитание матриц

   TMatrix         operator*    (TMatrix &);       //умножение матриц

   TMatrix         operator^    (TMatrix &);       //умножение матриц

   //(перемножение

   //соответствующих

   //элементов)

   TMatrix &       operator+=   (TMatrix &);       //присваивания

   TMatrix &       operator-=   (TMatrix &);

   TMatrix &       operator*=   (TMatrix &);

   TMatrix &       operator^=   (TMatrix &);

   TMatrix         getTranspose ();                //транспонирование

   TMatrix &       setSingle    (int n);           //сделать единичной

   TMatrix         operator+    (TYPE);            //операции со скалярами

   TMatrix         operator-    (TYPE);

   TMatrix         operator*    (TYPE);

   TMatrix         operator/    (TYPE);

   TMatrix &       operator+=   (TYPE);

   TMatrix &       operator-=   (TYPE);

   TMatrix &       operator*=   (TYPE);

   TMatrix &       operator/=   (TYPE);

   TMatrix         operator-    ();

   TYPE            operator%    (TMatrix &);       //скалярное умножение для

   //матриц-векторов

   int             readSize     (istream &);       //чтение размеров

   int             readArray    (istream &);       //чтение массива

   int             writeSize    (ostream &);       //запись размеров

   int             writeArray   (ostream &);       //запись массива

private:

   TYPE **         array;                          //элементы матрицы

   int             sizeRow;                        //кол-во строк

   int             sizeCol;                        //кол-во столбцов

   void            error        (int);             //сообщение об ошибке

};

template<class TYPE>

TMatrix<TYPE>::TMatrix()

{

   array=NULL;

   sizeRow=0;

   sizeCol=0;

}

template<class TYPE>

TMatrix<TYPE>::TMatrix(TMatrix<TYPE> &m)

{

   array=NULL;

   sizeRow=0;

   sizeCol=0;

   if(m.sizeRow>0 && m.sizeCol>0)

   {

      sizeRow=m.sizeRow;

      sizeCol=m.sizeCol;