Метод усовершенствованной простой итерации. Численное решение Системы Линейных Алгебраических Уравнений методом Гаусса

 
 

  Содержание 

 
 

 

   Метод усовершенствованной простой итерации.

 
 
 
 
 
 
 
 
 

Рисунок 1.   Геометрическое   представление   усовершенствованного метода последовательных приближений для 0 < f'(x) < 1. 

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

   , где   можно принять следующую формулу для х_n+1:  , где α > 1.

  Эта идея поясняется на рис. 1. Наилучшим выбором  ее следует признать тот, что изображен  на рисунке, так как тогда х_п+1 получается равным а. Попытаемся определить это наилучшее значение α.

  Заметим, что расстояние между х_п+1 и а равно , и так как у= х есть прямая линия, идущая под углом 45° к осям координат, расстояние между  f(a)  и f(x_n) также равно . Поэтому тангенс угла θ равен

  

  (1)

  С другой стороны,

  

  (2)

  и, используя  теорему о среднем значении, 

  

  где .

  Из (1) и (2) получаем значение α в виде

  

  (3)

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

  

 (4)

  Геометрически процесс отыскания следующего приближения, х_п+1, сводится к тому, что проводится хорда между точками и , и определяется точка ее пересечения с прямой у = х.

  Формула итерационного метода приобретает  при этом следующий вид:

  

        (5)

  где α  определяется по формулам (3) и (4).

  Возникает вопрос, как это усовершенствование влияет на сходимость метода. Из формулы (3) видно, что при должно получиться . Последовательные поправки слишком малы; так как α > 1, усовершенствованный метод увеличит эти поправки и ускорит сходимость вычислений.

  При имеем 1/2 < α < 1. В усовершенствованном методе все поправки уменьшаются на коэффициент, расположенный между 1/2 и 1; сходимость метода при этом, естественно; также улучшается.

  Более важны  случаи, когда простой метод последовательных приближений расходится. Если f'(х)<1, то α < 0. Каждая очередная поправка имеет неправильный знак и соответствующее приближение отстоит от а дальше, чем предыдущее. Так как, α для этого случая отрицательно, то в усовершенствованном методе знаки поправок изменяются нужным образом.

  Наконец, при  имеем 0 < α < 1/2. В этом случае поправки слишком велики; при усовершенствованном методе каждая поправка умножается на коэффициент, расположенный между 0 и 1/2. 

  //решение уравнения 2-log(x)-x

  #include <iostream.h>

  #include <stdio.h>

  #include <math.h> 

  float f(float x);

  float al(float x,float xpred);

  const double Eps = 0.00001; 

  int main ()

  {int h=0;

          float x=5,xt,osh; //начальное приближение

          float xpred=f(x);

              osh=fabs(xpred-x);

          while (osh>Eps)

          {xt=x+(f(x)-x)*al(x,xpred);

              osh=fabs(x-xt);

              xpred=x; x=xt;

              h++;

          printf("V %d cikle x=%f\n", h, x);

              }

         printf ("Otvet x=%f\n", x); //вывод ответа

          return 0;

  }

  //функция нахождение значения функции в точке

  float f(float x)

  {

          float y;

          y =  2-log(x);

          if (y<0) y=fabs(y);

          return y;

  }

  //функция нахождения коэффициента

  float al(float x,float xpred)

  {

        float al;

        al=(x-xpred)/(2*x-f(x)-xpred);

        if (al>1) al=1;

              return al;

  }

    

  

 

  

 
Численное решение  Системы Линейных Алгебраических Уравнений  методом Гаусса 

  Описание  метода

  Пусть исходная система выглядит следующим образом

  

  Матрица A называется основной матрицей системы, b — столбцом свободных членов.

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

  

  При этом будем считать, что базисный минор (ненулевой минор максимального  порядка) основной матрицы находится  в верхнем левом углу, то есть в него входят только коэффициенты при переменных x_j1,…, x_jr.

  Тогда переменные x_j1,…, x_jr называются главными переменными. Все остальные называются свободными.

  Если хотя бы одно число β_i≠0, где i > r, то рассматриваемая система несовместна.

  Пусть β_i=0 для любых i > r.

  Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений  системы на свой коэффициент при самом левом x (α_ij, i=1 где i — номер строки):

,

  где i=1,…,r, k=i+1,…,n.

  Если свободным  переменным системы (2) придавать все  возможные значения и решать новую  систему относительно главных неизвестных  снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают. 

  Следствия:

1. Если в совместной системе все переменные главные, то такая система является определённой.

Если количество переменных в системе превосходит  число уравнений, то такая система  является либо неопределённой, либо несовместной. 

  Условие совместности

  Упомянутое  выше условие β_i=0 для всех i>r может быть сформулировано в качестве необходимого и достаточного условия совместности:

  Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

  Теорема Кронекера-Капелли.

  Система совместна тогда и только тогда, когда ранг её основной матрицы равен  рангу её расширенной матрицы.

  Следствия:

  Количество  главных переменных равно рангу  системы и не зависит от её решения.

  Если ранг совместной системы равен числу  переменных данной системы, то она определена. 

  Алгоритм

  Алгоритм  решения СЛАУ методом Гаусса подразделяется на два этапа.

  На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

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

  Метод Гаусса требует порядка O(n³) действий.

  Этот метод  опирается на: 

  Теорема (о приведении матриц к ступенчатому виду).

  Любую матрицу  путём элементарных преобразований только над строками можно привести к ступенчатому виду. 

  Простейший  случай 

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

  

  Прямой  ход:

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

  Пример

                                       

#include <stdio.h>

#include <math.h>

#include <windows.h>

char buf[256];

char* RUS(const char* text)

{

   CharToOem(text, buf);

   return buf;

} 

void preobr(float **a,int n);

void vvod (float **a, int k);

void vivod(float **a, int k, int l);

void vivodio(float *otv, int n);

void resh(float **a, float *b, int n); 

int main()

{ int n;

      printf (RUS("Введите колличество неизвестных\n"));

scanf ("%d", &n);

float **mat=new float *[n];