Введение
Данная курсоваяработа включает в себя три итерационных метода решения систем линейныхалгебраических уравнений (СЛАУ):
1. МетодЯкоби (метод итераций).
2. МетодХолецкого.
3. Методверхней релаксации.
Также данная курсоваяработа включает в себя: описание метода, применение метода к конкретной задаче(анализ), код программы решения вышеперечисленных методов на языкепрограммирования Borland C++ Builder 6.
Описаниеметода
Метод решениязадачи называют итерационным, если в результате получают бесконечнуюпоследовательность приближений к решению. Основное достоинство итерационныхметодов состоит в том, что точность искомого решения задается. Число итераций,которое необходимо выполнить для получения заданной точности />, является основной оценкойкачества метода. По этому числу проводится сравнение различных методов.
Главнымнедостатком этих методов является то, что вопрос сходимости итерационногопроцесса требует отдельного исследования. Примером обычных итерационных методовслужат: метод итераций (метод Якоби), метод Зейделя, метод верхних релаксаций.
Начнем с методаитераций или как его ещё называют метода Якоби.
Существует сиcтема A·x = f (1), где матрица A = [aij](i, j = 1, 2, …m) имеет обратную матрицу; x = (x1,x2, x3,… xm) – вектор неизвестных, f –вектор свободных членов. Систему (1) нужно преобразовать к следующему виду: /> (2) i=1, 2,…, m, где />,/>, при этом aii />0.
Значение суммы считается равным 0, если верхний пределсуммирования меньше нижнего. Тогда при i=1 уравнение имеет вид: />(3). В методе Якоби исходятиз записи системы в виде (2), итерации при этом определяют следующим образом: />, (n=0, 1, …, n0, i=1, 2, …, m) (4).
Начальные значения />– (i=0, 1, …, m) задаются произвольно(в программе мы это проделываем, вводя функцию по генерации случайных чисел – «random»). Окончание итерационногопроцесса определяют либо заданием максимального числа итераций n0,либо следующим условием: />, где />>0. В качестве нулевого приближения в системе (4) примем />.
Если последовательность приближений x1(0),x2(0),…, xm(0), x1(1),x2(1),…, xm(1),…, x1(k),x2(k),…,xm(k)имеет предел />, />, то этот предел являетсярешением системы (2).
Достаточным условием сходимости решения системы (1) является то,что матрица A является матрицей с преобладающими диагональнымиэлементами, то есть />, i=1, 2, …, m.
Теперь рассмотрим второй итерационный метод – метод Зейделя, который является модификацией метода Якоби. Основная его идеязаключается в том, что при вычислении (k+1) – го приближениянеизвестной xi учитываются уже вычисленные ранее (k+1) –е приближения (x1 x2,…, xi-1).
Пусть дана приведенная линейная система: /> (i = 1, 2, …n)(5). Выбираются произвольно начальные приближения корней x1(0),x2(0),…, xn(0), чтобы они в какой-то мере соответствовали неизвестным x1,x2, x3,…, xn.
Предполагается, что k-е приближение />корней известно, тогда всоответствии с идеей метода строится (k+1) – е приближение по следующимформулам:
/>
/>
k=0,1,2,… (6)
Если выполняется достаточное условие сходимости для системы (5) –по строкам, то в методе Зейделя выгодно расположить уравнения (6) так, чтобыпервое уравнение системы имело наименьшую сумму модулей коэффициентов: />.
Теперь рассмотри 3 метод – метод верхних релаксаций.
Метод верхней релаксации – это есть метод Зейделя с заданнымчисловым параметром w.
Одним из наиболее распространенных одношаговых методов являетсяметод верхних релаксаций, который имеет следующий вид /> (7), где w заданный числовой параметр (0
Достоинством итерационного метода верхних релаксаций является то,что при его реализации программным путем алгоритм вычислений имеет простой види позволяет использовать всего один массив для неизвестного вектора.
Для получения расчетных формул (7) перепишем в виде: /> или в компонентной записиполучим /> (8) – это есть основнаявычислительная формула.
В выражение (8) />и /> входят одинаковым образом => при вычислениях они могут бытьзаписаны в один и тот же массив. При реализации метода верхних релаксацийиспользуется следующая форма записи алгоритма вычислений />.
Действительно, при последовательном нахождении элемента />(i+10 итерации) на каждом шаге будут использоваться найденные ранее значения,которые при k
Применениеметода к конкретной задаче (анализ)
Составляязадачи на языке программирования Borland C++ Builder 6 для реализации точных методов решения СЛАУ яучитывал разное количество уравнений в системе (размерность матрицы задавалравным nxn). Но для проверки результатов использовал систему уравнений:
/>
Вообщеговоря, процесс Зейделя сходится быстрее, чем метод Якоби. Бывает, что процессЗейделя сходится, когда простая итерация расходится и т.п. Правда, бывает инаоборот. Во всяком случае, достаточные условия сходимости для метода Якобидостаточны и для сходимости метода Зейделя. Реализовав программы из полученногоответа я увидел, что процесс Зейделя сходится быстрее. Это видно по количествуитераций полученных в программе при приближенной точности />=0,000001. Если для методаЯкоби они составляют 16, то для метода Зейделя они составляют 9.
Такжерассматривая метод верхней релаксации и сравнивая его с двумя другими методамивидно, что в методе верхней релаксации количество итераций зависит от заданногочислового параметра w. Задавая w=1, количество итерацийравно 9, уменьшая значение параметра от 1 количество итераций начинает расти, всвою очередь увеличивая параметр количество итераций тоже начинает расти.
Приведемтаблицу показывающих количество итераций (k) при разных значенияхпараметра w:w 0.1 0.4 0.8 0.9 1 1.1 1.2 1.3 1.7 1.9 k 16 15 14 13 9 13 14 15 16 16
Из всегоэтого можно сделать вывод, что итерационные методы сходятся быстрее, чем точныеметоды, о чем свидетельствуют как быстрое уменьшение невязок, так и уменьшениеизменений неизвестных.
Листингпрограммы
// –
#includevcl.h>
#pragmahdrstop
#include«Unit1.h»
//–
#pragmapackage (smart_init)
#pragmaresource «*.dfm»
#include
#include
TForm1*Form1;
intn=0, prov=0, k=0;
constx=100;
floatA[x] [x], B[x] [x];
floatC[x], Y[x];
float*X;
boolfl1=false;
floate;
floatv_sh;
//–
__fastcallTForm1:TForm1 (TComponent* Owner)
:TForm(Owner)
{
}
//–
void__fastcall TForm1: ButtonOkClick (TObject *Sender)
{
Memo1->Lines->Clear();
k=0;
TryStrToInt(Edit1->Text, n);
if(n>1)
{
StringGrid1->Enabled=true;
StringGrid1->RowCount=n;
StringGrid1->ColCount=n+1;
ButtonClear->Enabled=true;
ButtonOk->Enabled=false;
StringGrid1->Color=clWindow;
ButtonYakobi->Enabled=true;
ButtonZeydel->Enabled=true;
ButtonRelax->Enabled=true;
X=newfloat[n];
for(int i=0; i
{
for(int j=0; j
{
A[i][j]=NULL;
}
X[i]=NULL;
}
}
else
{
ShowMessage(«Число должно быть вещественного типа!»);
}
}
//–
void__fastcall TForm1: ButtonClearClick (TObject *Sender)
{
StringGrid1->Enabled=false;
StringGrid1->RowCount=0;
StringGrid1->ColCount=0;
ButtonClear->Enabled=false;
ButtonOk->Enabled=true;
StringGrid1->Color=clBtnFace;
ButtonYakobi->Enabled=false;
}
//–
void__fastcall TForm1: ButtonYakobiClick (TObject *Sender)
{
//TryStrToFloat(Edit2->Text, e);
Memo1->Lines->Clear();
e=StrToFloat(Edit2->Text);
for(int i=0; i
{
for(int j=0; j
{
TryStrToFloat(StringGrid1->Cells[j] [i], A[i] [j]);
}
}
for(int i=0; i
{
for(int j=0; j
{
if(A[i] [j]==NULL)
{
ShowMessage(«Ошибка! Есть пустые ячейки!»);
fl1=true;
i=n;
break;
}
}
}
if(!fl1) {
for(int i=0; i
{
for(int j=0; j
{
if(i!=j) B[i] [j]=(-1)*A[i] [j]/A[i] [i];
else
{
B[i][j]=0;
C[i]=A[i][n]/A[i] [i];
}
}
}
for(int i=0; i
floats=0;
k=0;
do
{
prov=0;
for(int i=0; i
{
Y[i]=X[i];
for(int j=0; j
{
s+=B[i][j]*X[i];
}
X[i]=s+C[i];
s=0;
}
for(int i=0; i
{
if(fabs(X[i] – Y[i])
}
k++;
}
while(prov!=n);
Memo1->Lines->Add(» МЕТОДЯКОБИ»);
Memo1->Lines->Add(«»);
Stringp=»»;
Memo1->Lines->Add(«Промежуточная матрица:»);
for(int i=0; i
{
p=»»;
for(int j=0; j
{
p+=FloatToStr(B[i] [j])+»»;
}
Memo1->Lines->Add(p);
}
Memo1->Lines->Add(«»);
Memo1->Lines->Add(«КорниСЛАУравны:»);
for(int i=0; i
{
if(X[i]!=NULL)
{
Memo1->Lines->Add(«x»+IntToStr (i+1)+» = «+FloatToStr (X[i]));
}
else
{
Memo1->Lines->Add(«Неткорней!»);
break;
}
}
Memo1->Lines->Add(«»);
Memo1->Lines->Add(«Количествоитераций= «+FloatToStr(k));
}
}
//–
void__fastcall TForm1: ButtonExitClick (TObject *Sender)
{
Close();
}
//–
void__fastcall TForm1: RadioButton2Click (TObject *Sender)
{
ButtonYakobi->Visible=false;
ButtonZeydel->Visible=true;
ButtonRelax->Visible=false;
}
//–
void__fastcall TForm1: RadioButton1Click (TObject *Sender)
{
ButtonYakobi->Visible=true;
ButtonZeydel->Visible=false;
ButtonRelax->Visible=false;
}
//–
void__fastcall TForm1: ButtonZeydelClick (TObject *Sender)
{
Memo1->Lines->Clear();
k=0;
e=StrToFloat(Edit2->Text);
for(int i=0; i
{
for(int j=0; j
{
TryStrToFloat(StringGrid1->Cells[j] [i], A[i] [j]);
}
}
for(int i=0; i
{
for(int j=0; j
{
if(A[i] [j]==NULL)
{
ShowMessage(«Ошибка! Есть пустые ячейки!»);
fl1=true;
i=n;
break;
}
}
}
if(!fl1) {
for(int i=0; i
{
for(int j=0; j
{
if(i!=j) B[i] [j]=(-1)*A[i] [j]/A[i] [i];
else
{
B[i][j]=0;
C[i]=A[i][n]/A[i] [i];
}
}
}
for(int i=0; i
{
X[i]=rand();
}
k=0;
floats=0;
for(int i=0; i
{
for(int j=0; j
{
s+=B[i][j];
}
Y[i]=s;
s=0;
}
s=Y[0];
for(int i=1; i
{
if(s
Y[i]=0;
}
if(s
{
do
{
s=0;
for(int i=0; i
{
Y[i]=X[i];
}
for(int i=0; i
{
s=C[i];
for(int j=0; j
{
s+=X[j]*B[i][j];
}
X[i]=s;
}
prov=0;
for(int i=0; i
{
if(fabs(X[i] – Y[i])
}
k++;
}
while(prov!=n);
Memo1->Lines->Add(» МЕТОДЗЕЙДЕЛЯ»);
Memo1->Lines->Add(«»);
Stringp=»»;
Memo1->Lines->Add(«Промежуточная матрица:»);
for(int i=0; i
{
p=»»;
for(int j=0; j
{
p+=FloatToStr(B[i] [j])+»»;
}
Memo1->Lines->Add(p);
}
Memo1->Lines->Add(«»);
Memo1->Lines->Add(«КорниСЛАУравны:»);
for(int i=0; i
{
if(X[i]!=NULL)
{
Memo1->Lines->Add(«x»+IntToStr (i+1)+» = «+FloatToStr (X[i]));
}
else
{
Memo1->Lines->Add(«Неткорней!»);
break;
}
}
Memo1->Lines->Add(«»);
Memo1->Lines->Add(«Количествоитераций= «+FloatToStr(k));
}
else{Memo1->Lines->Add («СЛАУ является не сходимой!»);}
}
}
//–
void__fastcall TForm1: RadioButton3Click (TObject *Sender)
{
ButtonYakobi->Visible=false;
ButtonZeydel->Visible=false;
ButtonRelax->Visible=true;
}
//–
void__fastcall TForm1: ButtonRelaxClick (TObject *Sender)
{
//TryStrToFloat(Edit2->Text, e);
v_sh=StrToFloat(Edit3->Text);
e=StrToFloat(Edit2->Text);
Memo1->Lines->Clear();
k=0;
for(int i=0; i
{
for(int j=0; j
{
TryStrToFloat(StringGrid1->Cells[j] [i], A[i] [j]);
}
}
for(int i=0; i
{
for(int j=0; j
{
if(A[i] [j]==NULL)
{
ShowMessage(«Ошибка! Есть пустые ячейки!»);
fl1=true;
i=n;
break;
}
}
}
if(!fl1) {
floatvsp=0, alp=0;
for(int i=0; i
{
for(int j=0; j
{
if(i!=j) B[i] [j]=(-1)*A[i] [j]/A[i] [i];
else
{
B[i][j]=0;
C[i]=A[i][n]/A[i] [i];
}
}
}
float*sq_z=new float[n];
float*sq_y=new float[n];
for(int i=0; i
{
sq_z[i]=rand();
}
for(int i=0; i
for(int i=0; i
vsp=C[0];
for(int j=0; j
{
vsp+=sq_z[j]*B[0][j];
}
sq_z[0]=vsp;
for(int i=0; i
{
for(int j=0; j
{
vsp+=B[i][j];
}
Y[i]=vsp;
vsp=0;
}
vsp=Y[0];
for(int i=1; i
{
if(vsp
Y[i]=0;
}
if(vsp
{
do
{
for(int i=0; i
{
Y[i]=X[i];
}
for(int i=0; i
{
vsp=C[i];
for(int j=0; j
{
vsp+=sq_z[j]*B[i][j];
alp+=B[i][j]*sq_y[i];
}
sq_z[i]=vsp;
sq_y[i]=alp+C[i];
vsp=0;
alp=0;
X[i]=v_sh*sq_z[i]+(1-v_sh)*sq_y[i];
}
prov=0;
for(int i=0; i
{
if(fabs(X[i] – Y[i])
}
k++;
}
while(prov!=n);
Memo1->Lines->Add(» МЕТОДВЕРХНЕЙРЕЛАКСАЦИИ»);
Memo1->Lines->Add(«»);
Stringp=»»;
Memo1->Lines->Add(«Промежуточная матрица:»);
for(int i=0; i
{
p=»»;
for(int j=0; j
{
p+=FloatToStr(B[i] [j])+»»;
}
Memo1->Lines->Add(p);
}
Memo1->Lines->Add(«»);
Memo1->Lines->Add(«КорниСЛАУравны:»);
for(int i=0; i
{
if(X[i]!=NULL)
{
Memo1->Lines->Add(«x»+IntToStr (i+1)+» = «+FloatToStr (X[i]));
}
else
{
Memo1->Lines->Add(«Неткорней!»);
break;
}
}
Memo1->Lines->Add(«»);
Memo1->Lines->Add(«Количествоитераций= «+FloatToStr(k));
}
else{Memo1->Lines->Add («СЛАУ является не сходимой!»);}
}
}
// –
Результатырасчета
МЕТОД ЯКОБИ
МЕТОД ЗЕЙДЕЛЯ
МЕТОД ВЕРХНЕЙ РЕЛАКСАЦИИ
Промежуточная матрица:
0 -0,100000001490 -0,100000001490 0
-0,200000002980 0 -0,100000001490 0
-0,200000002980 -0,200000002980 0 0
Корни СЛАУ равны:
x1 = 1
x2 = 1
x3 = 1,00000011920929
Количество итераций = 16
Промежуточная матрица:
0 -0,100000001490 -0,100000001490 0
-0,200000002980 0 -0,100000001490 0
-0,200000002980 -0,200000002980 0 0
Корни СЛАУ равны:
x1 = 1
x2 = 0,99999988079071
x3 = 0,999999940395355
Количество итераций = 9
Промежуточная матрица:
0 -0,100000001490 -0,100000001490 0
-0,200000002980 0 -0,100000001490 0
-0,200000002980 -0,200000002980 0 0
Корни СЛАУ равны:
x1 = 1,00000011920929
x2 = 0,99999988079071
x3 = 0,999999940395355
w=1
Количество итераций = 9