Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений
Содержание.
Введение……………………………………………………….
1. Метод градиента
(метод скорейшего спуска) для
случая системы нелинейных
2. Метод скорейшего
спуска для случая системы
линейных уравнений………………………………
3. Свойства приближений метода скорейшего спуска……17
Заключение……….………….……………………………
Список использованной литературы…………….………….26
Приложение 1……………………………………………………27
Приложение 2……………………………………………………28
Приложение 3……………………………………………………32
Введение
Задачи численного решения систем линейных алгебраических уравнений (ЛАУ) и систем нелинейных численных уравнений многочисленны и весьма разнообразны. Это в первую очередь объясняется многообразием матриц систем ЛАУ и просто матриц для которых необходимо проводить вычисления.
В настоящее время не существует методов, которые в одинаковой мере были бы хороши для всех систем ЛАУ. Почти все методы являются ориентированными и учитывают тем или иным образом специальные свойства матриц систем ЛАУ.
В курсовом проекте я рассматриваю метод скорейшего спуска. Этот метод не входит в число методов, которые широко используются и часто встречаются в литературе. Он реже используется в практике вычислений, но тем не менее содержит глубокие идеи и входит в основы теории вычислительной алгебры.
Метод градиента (метод скорейшего спуска) для случая системы нелинейных уравнений.
Пусть имеется система нелинейных уравнений:
(1)
Систему (1) удобнее записать в матричном виде:
где - вектор – функция; - вектор – аргумент.
Предположим, что функции действительны и непрерывно дифференцируемы в их общей области определения. Рассмотрим функцию:
(3)
Очевидно, что каждое решение системы (1) обращает в нуль функцию U(x); наоборот, числа x1, x2, ..., xn, для которых функция U(x) равна нулю, являются корнями системы (1).
Будем предполагать, что система (1) имеет лишь изолированное решение, которое представляет собой точку строгого минимума функции U(x). Таким образом, задача сводится к нахождению минимума функции U(x) в n-мерном пространстве
.
Пусть x – вектор-корень системы (1) и x(0) – его нулевое приближение. Через точку x(0) проведем поверхность уровня функции U(x). Если точка x(0) достаточна близка к корню х, то при наших предположениях поверхность уровня
U(x)=U(x(0))
будет похожа на эллипсоид.
Из точки х(0) двигаемся по нормали к поверхности U(x)=U(x(0)) до тех пор, пока эта нормаль не коснется в некоторой точке х(1) какой-то другой поверхности уровня.
U(x)=U(x(1)).
Затем, отправляясь от точки х(1), снова двигаемся по нормали к поверхности уровня U(x)=U(x(1)) до тех пор, пока эта нормаль не коснется в некоторой точке х(2) новой поверхности уровня U(x)=U(x(2)) и.т.д.
Так как U(x(0))>U(x(1))>U(x(2))>..., то, двигаясь по такому пути, мы быстро приближаемся к точке с наименьшим значением U (“дно ямы”), которая соответствует искомому корню х системы (1). Обозначим через
градиент функции U(x).
( Градиент есть вектор, приложенный
в точке х, имеющий
Справедлива формула
где ei(i=1,2,…,n)-орты пространства En)
Из векторных треугольников OM0M1,
Остается определить
множители
для этого рассмотрим скалярную функцию
Функция Ф(l) дает изменение уровня функции U вдоль соответствующей нормали к поверхности уровня в точке х(р). Множитель l=lр надо выбрать таким образом, чтобы Ф(l) имела минимум. Беря производную по l и приравнивая ее к нулю, получаем уравнение
. (4)
Наименьший положительный корень уравнения (4) и даст нам значение lр. Уравнение (4), вообще говоря, нужно решать численно. Поэтому укажем метод приближенного нахождения чисел lр. Будем считать, что l - малая величина, квадратом и высшими степенями которой можно пренебречь. Имеем:
Ф(l)=
Разлагая функции по степеням l с точностью до линейных членов, получим:
где
Отсюда
Следовательно
где
-матрица Якоби вектор-функции f.
Далее, имеем:
Отсюда:
где W¢(x)-транспонированная матрица Якоби.
Поэтому окончательно:
(5)
где для краткости положено
причем
(p=0, 1, 2, ...). (6)
Если допустить, что функция f(
1
Пример 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, ...), причем
при . 2
Пример
Методом скорейшего спуска решить систему уравнений
(4)
Так как в матрице системы преобладают диагональные элементы, то в качестве начального вектора х(0) примем вектор, координаты которого представляют собой округленные значения корней системы:
Отсюда, например,
Следовательно,
Далее,
Применяя формулу (3), получаем:
Отсюда
причем
Аналогично находятся дальнейшие приближения и соответствующие невязки:
;
Заметим, что в данном случае процесс приближений сходится медленно: после пятого приближения мы еще далеки от точных корней системы (4):
Свойства приближении метода скорейшего спуска.
Исследуем свойства последовательности векторов х0, х1, х2… Для этой цели нам потребуются две леммы, которые доказываются ниже.
Леммы доказаны для системы Ах=f c положительноопределенной симметрической матрицей А.
Тогда вычислительная схема имеет вид:
(5)
К системам с нессиметричным матрицам легко перейти после умножения системы на матрицу А¢.
А¢Ах=А¢f
При этом в качестве невязки мы должны взять вектор
(Чтобы не путаться
в переобозначениях в
Лемма 1.
Если ai –некоторые положительные числа, а gi некоторые числа, удовлетворяющие неравенствам
то справедливо неравенство
(1*)
Доказательство:
Введем обозначение
и
тогда неравенство (1*) примет вид
(2*)
отметим, что
и
Так как среднее геометрическое меньше среднего арифметического или равно ему, то будет
(3*)
Функция
принимает наибольшее значение на отрезке
при
Это значение в обоих случаях равно
Значит,
(4*)
при всех i=1, 2, ... n.
Теперь из (3*) в силу (4*) получим
Лемма доказана.
Введем в рассмотрение понятие функции ошибки, определив ее формулой
G(x)=(Ae,e) (5*)
Где e=х*-х – вектор ошибки, х*-точное решение системы Ах=f.
Имеет место
Лемма 2.
Последовательность значений функции ошибки G(x(0)), G(x(1)),..., G(x(p)). Где х(р) определяются формулами (5*) , стремится к 0 при р стремящемся к бесконечности.
Доказательство:
В силу формул (5) имеем
значит,
(6*)
где
Оценим снизу величину qp.
Пусть
-собственные значения матрицы А, и u1, u2, ..., un –принадлежащие им собственные векторы, ортогональные друг к другу и нормированные так, что (ui,ui)=1 при i=1, 2, ..., n.
Все li >0 , т.к. А - положительно определенная матрица.
Пусть
Разложим вектор rp по собственным векторам матрицы А:
rp=c1u1+c2u2+...+cnun (7*)
так как под rp мы понимаем ненулевой вектор невязок системы, то в разложении (7*) не все с равны 0. имеем
Следовательно
Теперь для qp получим
В силу формулы (1*) отсюда следует
Значит
Далее получим
или
(8*)
Коэффициент <1, поэтому из (8*) следует, что
при .
Лемма доказана.
Теорема
Последовательные приближения х0, х1, х2…, построенные по методу скорейшего спуска, сходятся к решению системы Ax=f со скоростью геометрической прогрессии.
Доказательство
Из Леммы 2 следует, что
при
А это означает, что
при ,так как матрица А – положительноопределенная. Определим теперь скорость сходимости. Имеем
(9*)
где e(p) =x(*)-x(p).
Из (8*) и (9*) следует оценка
Означающая, что стремится к нулю со скоростью геометрической прогрессии. Теорема доказана.3
Заключение.
В курсовом проекте был рассмотрен метод скорейшего спуска для нахождения корней линейных и нелинейных алгебраических уравнений. В ходе работы, мы на примерах убедились, что этот метод позволяет находить приближенные корни систем с достаточной точностью и за конечное число шагов. Отсюда можно сделать вывод, что метод можно применять для эффективного решения реальных задач.
список использованной литературы.
- Демидович Борис Павлович, Марон Исаак Абрамович “Основы вычислительной математики” – М.: Наука, 1966 г. - 664 с.
- Крылов Владимир Иванович, Бобков Владимир Васильевич, Монастырный Петр Ильич “Начала теории вычислительных методов. Линейная алгебра и нелинейные уравнения.” – Минск: Наука и техника, 1985г.-280с.
3.Симонович Сергей
Виталиевич, Евсеев Георгий Александрович,
“Занимательное
Приложение 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> &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,
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(
{
array=NULL;
sizeRow=0;
sizeCol=0;
if(m.sizeRow>0 && m.sizeCol>0)
{
sizeRow=m.sizeRow;
sizeCol=m.sizeCol;
- Метод гражданского права
- Метод гражданского права
- Метод гражданского права
- Метод группировки, как основа статистической сводки
- Метод группировок в изучении трудовых ресурсов
- Метод группировок в статистике, его значение в использовании социально-экономических явлений по материалам: ОАО «Ливенский завод противо
- Метод группировок и его место в системе статистических методов
- Метод Гаусса
- Метод Гаусса
- Метод Гаусса решения СЛАУ
- Метод геоинформационных систем в географической науке
- Метод гілок та меж для рішення задач цілочисельного програмування
- Метод главных компонент
- Метод главных компонент
