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

Вступ

Бурхливий розвиток новітньої техніки й все більше впровадження сучасних розділів математики незмірно підвищили вимоги до математичної підготовки фахівців і вдосконалюванню техніки програмування. Програмістам, що займаються прикладним, системним або Web програмуванням необхідно чітко бачити алгоритм створюваного проекту, будь те текстовий процесор або серйозна операційна система. Математичне утворення дає програмістові можливість простіше й оптимальніше побудувати як сам алгоритм, так і програму.

Сьогодні серйозні компанії працюють над новими мовами програмування й засобами реалізації коду. Так, завдяки Б.Страуструпу було уведено об’єктно - орієнтоване програмування,  створений їм мова C++ відкрив перед програмістами нові обрії. Але час не коштує на місці й C++ перестає бути популярним, на зміну йому приходить JAVA, що має винятково класову структуру, написані на ньому програми займають менший об'єм пам'яті й виконуються набагато швидше. Але деякі мови не мають об’єктно - орієнтованої структури еволюціонували й представляють саму перспективну галузь серед інших мов, такими мовами є Delphi (Остання версія якого - 2006), Visual Basic 2005(Visual Studio 2005).

У своєму проекті я буду використовувати Borland C++ версії 4.5, тому що вважаю його найбільш оптимальним для поставленої мною задачі.

1.1 Загальна характеристика методів рішення систем лінійних рівнянь.

Способи вирішення систем лінійних рівнянь в основному розділяються на дві групи: 1) точні методи, що представляють собою кінцеві алгоритми для обчислення корінь системи ( до таких методів ставляться: правило Крамера, метод Гаусса, метод головних елементів, метод квадратних корінь і ін.), і 2) ітераційні методи, що дозволяють одержувати корінь системи із заданою точністю, шляхом збіжних нескінченних процесів (до їхнього числа належать метод ітерацій, метод Зейделя, метод релаксації і ін.).

Внаслідок неминучих округлень результати навіть точних методів є наближеними, причому оцінка погрішностей корінь у загальному випадку скрутна. При використанні ітераційних процесів, поверх того, додається погрішність методу.

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

1.2 Метод релаксації змінних систем лінійних рівнянь

П.З.:

Дана система лінійних рівнянь, необхідно знайти  та ін.

Нехай маємо наступну систему лінійних рівнянь:

                                                         (1)

Перетворимо цю систему в такий спосіб: перенесемо вільні члени ліворуч і розділимо перше рівняння на -  і т.д. Тоді одержимо систему, приготовлену до релаксації,

                                                       (2)

де

    и.

Нехай  початкове наближення рішення системи (2). Підставляючи ці значення в систему (2), одержимо нев'язання

                                                      (3)

Якщо однієї з невідомих  дати приріст  зменшиться на величину  збільшаться на величини  в 0, досить величині  дати приріст

і ми будемо мати:

и

          при

Метод релаксації (по-російському: ослаблення) у його найпростішій формі полягає в тім, що на кожному кроці перетворюють у нуль максимальну по модулі нев'язання шляхом зміни значень відповідного компонента наближення. Процес закінчується, коли всі нев'язання останньої перетвореної системи будуть рівні 0 із заданою точністю. Питання про збіжність цього процесу ми залишаємо без розгляду .

1.3 Використання метода релаксації змінних в системах лінійних рівнянь на прикладі

Приклад. Методом релаксації вирішити систему

                                                             (4)

роблячи обчислення із двома десятковими знаками.

Рішення. Приводимо систему (4) до виду, зручному для релаксації

Вибираючи як початкові наближення корінь нульові значення

Знаходимо відповідні їм нев'язку

Відповідно до загальної теорії думаємо:

Звідси одержуємо нев'язку

Далі, думаємо

і т.д. Відповідні результати обчислень наведені в таблиці.

Підсумовуючи всі прирости

Для контролю підставляємо знайдені значення корінь у вихідні рівняння; у цьому випадку система вирішена точно.

Висновки

Я навчився розв’язувати системи лінійних рівнянь методом релаксації змінних, та закріпив отримані навички розробкою програми  на мові Borland C++ 4.5.

Додаток А

Вирішити систему лінійних рівнянь методом релаксації змінних.

Лістинг програми 1.1:

#include<iostream.h>

#include<math.h>

int maximal(int n,double R0[]);

void main(){

int i,j,n,f,k,iter;

double S,det;

cout<<"Введите размерность матрицы(матрица должна быть квадратной)= ";cin>>n;

double *x=new double [n];

double **b=new double *[n];

for(i=0;i<n;i++)

  b[i]=new double[n+1];

double **a=new double *[n];

for(i=0;i<n;i++)

  a[i]=new double[n+1];

cout<<"Введите количество итераций:";

cin>>iter;

cout<<"Введите расширенную матрицу:\n";

for(i=0;i<n;i++){

      for(j=0;j<=n;j++)

            cin>>b[i][j];

}

cout<<"Подготавливаю матрицу к релаксации...\n";

for(i=0;i<n;i++){

      for(j=0;j<n;j++)

        a[i][j]=-b[i][j]/b[i][i];

      a[i][n]=b[i][n]/b[i][i];

}

for(i=0;i<n;i++){

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

            cout<<"  "<<a[i][j]<<" || ";

cout<<"\n";

}

double *x0=new double [n];

for(i=0;i<n;i++)

  x[i]=0.0;

double *R0=new double [n];

cout<<"Введите значения начальных приближений:\n";

for(i=0;i<n;i++)

      cin>>x0[i];

S=0.0;

for(i=0;i<n;i++){

      for(j=0;j<n;j++)

        S=S+a[i][j]*x0[i];

}

for(i=0;i<n;i++){

      R0[i]=a[i][n]-x0[i]+S;

      cout<<"R("<<i<<")="<<R0[i]<<" | ";

}

f=maximal(n,R0);

det=R0[f];

for(k=0;k<iter;k++){

cout<<"det{"<<k<<"}="<<det<<"\n";

 for(i=0;i<n;i++){

      if(i!=f) R0[i]=R0[i]+a[i][f]*det;

       else R0[i]=R0[i]-det;

 }

 for(i=0;i<n;i++)

            cout<<"R["<<i+1<<"]="<<R0[i]<<"    ";

x[f]=x[f]+det;

f=maximal(n,R0);

det=R0[f];

}

cout<<"\n";

for(i=0;i<n;i++)

  cout<<"X{"<<i+1<<"}="<<x[i]<<"\n";

delete []x;

delete []R0;

delete []x0;

delete []a;

}

int maximal(int n,double R0[]){

int i,f;

f=0.0;

for(i=0;i<n-1;i++){

  if(R0[i+1]>R0[i]) f=i+1;

}

return f;

}