Исследование метода Холецкого для СЛАУ

Размещено на http://www.allbest.ru/

1

Содержание

Введение

1. Постановка задачи, математическая формулировка метода

2. Описание программного обеспечения

3. Описание тестовых задач

4. Анализ результатов

Заключение

Список литературы

Введение

Целью данного проекта является исследование метода Халецкого для решения систем линейных алгебраических уравнений. В ходе работы будет приведена математическая интерпретация метода, создана программа на языке программирования Turbo PASCAL, и выведены необходимые зависимости в графической форме с использованием матрично-ориентированной системы MatLAB. Будут проанализированы результаты и сделаны соответствующие выводы.

Исходные данные для проектирования:

Исследовать влияние мерности матрицы А, её обусловленности, разрешённости на точность полученного решения (оценивается по невязке ? = AX - b, где X - полученное решение).

Перечень графического материала:

График зависимости точности полученного решения от мерности матрицы А.

1. Постановка задачи, математическая формулировка метода

Рассмотрим систему линейных уравнений, записанную в матричном виде:

Ах = b,

где A=(аij)--квадратная матрица порядка n (i, j=1, 2, …, n) и

векторы-столбцы.

Представим матрицу A в виде произведения нижней треугольной матрицы В и верхней треугольной матрицы С с единичной диагональю, т.е. А=ВС.

Тогда элементы bij и сij будут определяться по формулам

Исходное уравнение можно записать в следующем виде:

BCx=b

Произведение Сx (матрицы С на вектор-столбец x) является вектором-столбцом, который обозначим через y:

Сx=y

Отсюда искомый вектор x может быть вычислен из цепи уравнений Ву=b, Сх=у. Так как матрицы В и С треугольные, то системы (3) легко решаются, а именно.

Из формул видно, что числа уi выгодно вычислять вместе с коэффициентами cij. Эта схема вычислений называется схемой Халецкого. В схеме применяется обычный контроль с помощью сумм.

Схема Халецкого удобна для работы на клавишных вычислительных машинах, так как в этом случае операции «накопления» можно проводить без записи промежуточных результатов.

Пример. Решить систему:

3x1 - x2 - x3 + 2x4 = 6

-5x1- x2 + 3x3 - 4x4 = -12

2x1 +x3 -x4 = 1

x1- 5x2 + 3x3 - 3x4 = 3

Решение.

Результаты вычислений записываем в табл. 1. Она состоит из двух частей:

1) левая половина, в которой дается схема записи результатов вычислений;

2) правая половина, в которой записываются результаты вычислений согласно указанной схеме.

Порядок заполнения таблицы.

1) В первый раздел табл. 1 вписываем матрицу коэффициентов системы, ее свободные члены и контрольные суммы.

2) Элементы столбца х1 из раздела I переносим в столбец х1 раздела II, так как bi1=а i1 (i=1, 2, 3, 4).

3) Вычисляем элементы первой строки раздела II. Для этого делим все элементы первой строки раздела I на элемент а11 = b11, в нашем случае на 3.

Имеем:

4) Заполняем столбец х2 раздела II, начиная со второй строки. Пользуясь формулами (1), определяем bj2.

5) Заполняем вторую строку раздела II, определяя с2j для j=3, 4, 5, 6 по формулам.

6) Заполняем столбец Х3, вычисляя его элементы b33 и b43 по формулам (1).

7) Аналогично продолжаем процесс до тех пор, пока не будет заполнен раздел II.

Таким образом, заполнение раздела II происходит способом «ёлочки»: столбец--строка, столбец--строка и т. д.

8) Определяем уi и хi (i=1, 2, 3, 4) по формулам и записываем в раздел III.

9) Текущий контроль осуществляем с помощью столбца ?, над которым производим те же действия, что и над столбцом свободных членов.

2. Описание программного обеспечения

В качестве основного языка программирования для решения СЛАУ по методу Халецкого был выбран язык Turbo PASCAL. Программа, производящая все необходимые расчёты, дана ниже с комментариями:

Program XALETSKI;

{ СХЕМА ХАЛЕЦКОГО }

Uses Crt;

Const n=2 { Число уравнений в системе };

Type Masiv = array[1..n] of real;

Var A:array[1..n,1..n+1] of real; { Матрица коэффициентов aij }

B:array[1..n,1..n] of real; { Матрица B }

C:array[1..n,1..n+1] of real; { Матрица С }

X { массив корней }:Masiv;

Y { Массив чисел y }:Masiv;

i,j,m,k:integer;

fl:text; { Файловая переменная, в которую выводится результат }

Sum,Sum1:real;

BEGIN

Clrscr;

Writeln(' КОЭФФИЦИЕНТЫ УРАВНЕНИЙ: ');

for i:=1 to n do

for j:=1 to n+1 do

begin

Write(' A(',i,',',j,')= '); Read(A[i,j]);{Ввод коэффициентов aij}

end;

Writeln;

Writeln;

{ Вывод на печать исходной матрицы }

Assign(fl,'con');

Rewrite(fl);

Writeln(fl,' ИСХОДНАЯ МАТРИЦА');

for i:=1 to n do

begin

for j:=1 to n do Write(fl,A[i,j]:6:3,' * X',j,' ');

Writeln(fl,'= ', A[i,n+1]:6:3);

end;

Writeln(fl);

{ Присваивание первому столбцу матрицы B первого столбца исходной матрицы и определение коэффициентов c1,j }

for i:=1 to n do B[i,1]:=A[i,1];

for j:=2 to n+1 do C[1,j]:=A[1,j] / B[1,1];

Y[1]:=A[1,n+1] / B[1,1]; { Определение первого значения y }

FOR m:=2 TO n DO

BEGIN

j:=m;

i:=m;

Repeat

{ Вычисление суммы }

Sum:=0;

k:=1;

Repeat

Sum:=Sum + B[i,k] * C[k,j];

k:=k+1;

Until k>j-1;

{ Вычисление коэффициента матрицы B }

B[i,j]:=A[i,j] - Sum;

i:=i+1;

Until i>n;

i:=m;

j:=m+1;

Repeat

{ Вычисление суммы для С и Y }

Sum:=0; Sum1:=0;

k:=1;

Repeat

Sum:=Sum + B[i,k] * C[k,j];

Sum1:=Sum1 + B[i,k] * Y[k];

k:=k+1;

Until k>i-1;

{ Вычисление коэффициента матрицы C }

C[i,j]:=1 / B[i,i] * (A[i,j] - Sum);

j:=j+1;

Until j>n+1;

{ Вычисление коэффициента Y }

Y[i]:=1 / B[i,i] * (A[i,n+1] - Sum1);

END;

{ Вычисление корней системы, начиная с максимального индекса и их печать }

X[n]:=Y[n];

ClrScr;

Writeln(fl,'РЕЗУЛЬТАТЫ РАСЧЕТОВ:');

Writeln(fl,'X',n,'=',X[n]:9:5);

for i:=n-1 downto 1 do

Begin

Sum:=0; k:=i+1;

While k<=n do

Begin

Sum:=Sum + C[i,k] * X[k];

k:=k+1;

End;

X[i]:=Y[i] - Sum;

Writeln(fl,'X',i,'=',X[i]:9:5);

End;

Close(fl);

END.

Программа универсальна, т. к. она получает решение по методу для любого количества уравнений в системе.

Демонстрация работы программы:

Решим пример, рассмотренный подробно в первой части (стр. 5):

3x1 - x2 - x3 + 2x4 = 6

-5x1- x2 + 3x3 - 4x4 = -12

2x1 +x3 -x4 = 1

x1- 5x2 + 3x3 - 3x4 = 3

Ввод данных на последующую обработку:

Полученное решение (начиная с максимального индекса):

Это в точности совпадает с ранее полученным решением.

3. Описание тестовых задач

матрица слау метод холецкий

Исследование влияния обусловленности и разрешённости матрицы А на точность полученного решения

Матрица А называется плохо обусловленной, если существует такая матрица В, что при небольших возмущениях коэффициентов матриц А и В произойдут большие изменения в Х = А •В. Система А • Х = В плохо обусловлена, когда матрица А плохо обусловлена. В этом случае численные методы приближённого вычисления могут привести к большим ошибкам.

Плохая обусловленность возникает тогда, когда матрица А “почти вырождена” и определитель а близок к нулю. Плохая обусловленность также имеет место в системах двух уравнений, когда две линии почти параллельны.

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

Исследование влияния мерности матрицы А на точность полученного решения

Для проведения необходимого исследования определим входные параметры, задающие текущие состояния матрицы, исходя из того, что необходимо исключить влияние остальных признаков.

Оценку проведём по невязке ? = А • Х - В, где Х - полученное решение.

Начиная с двухмерной матрицы будем производить её последовательное наращивание до мерности n = 10 по следующему шаблону.

Выбор чисел случаен, т. к. это отражает более истинное влияние мерности матрицы на точность получаемого решения.

По аналогичному принципу наращиваем матрицу В (матрица-столбец свободных членов), т. е. В для

n = 10 имеет вид

Решения, полученные программой (индекс у Х - текущая мерность матрицы):

X2 = X3 = X4 =

-0.71429 2.23810 2.72414

0.85714 -5.04762 -9.05747

2.95238 6.59770

X5 = -0.85057

-0.89227

3.47697

-3.04607

3.15946

-1.07016

X6 = X7 = X8 = X9 = X10 =

-1.6457 -2.6659 0.4816 -12.9194 2.5455

-16.1784 -32.2604 -2.3883 -46.3986 4.0419

13.5956 31.9167 0.8037 23.2784 -2.8554

-14.2753 -33.6703 0.4085 -17.2257 2.4474

-7.5735 -16.3797 0.0168 -3.5706 0.5716

18.6508 41.7992 0.6833 17.8948 -2.0347

-6.3200 0.9089 26.3874 -2.2296

- 0.6002 -24.8276 2.7132

21.6032 -3.5153

1.0941

Точность решения оцениваем так: Е1 = ? ? и Е2 = max ¦? ¦.

Для удобства и наглядности расчётов создадим разработочную таблицу, предварительно подсчитав точность с использованием MatLAB

Мерность, n	E1 • 10	E2 • 10
2	0,7	0,1
3	0,81	0,2
4	1,53	0,4
5	2,44	0,5
6	4,28	1,08
7	6,43	1,1
8	7,42	0,6
9	7,83	0,7
10	7,92	0,3

Получение первой зависимости:

X=[2 3 4 5 6 7 8 9 10]

Y=[0.7 0.81 1.53 2.44 4.28 6.43 7.42 7.83 7.92]

plot(X,Y)

Строим вторую зависимость:

X=[2 3 4 5 6 7 8 9 10]

Y=[0.1 0.2 0.4 0.5 1.08 1.1 0.6 0.7 0.3]

plot(X,Y)

4. Анализ результатов

Видим, что при увеличении мерности матрицы происходит неоднозначное изменение зависимости полученного решения. Максимальные значения величины ошибки приходится на n = 6, 7. До этого значения n ошибка увеличивается скачкообразно. После этого значения Е2 (погрешность отдельно взятого решения) стремится к определённому значению, лежащему в пределах 0,3-0,7 (•10), хотя наблюдается тенденция к её дальнейшему снижению. Так и ошибка Е1 перестаёт значительно расти, приобретая приращение, измеряемое десятыми долями (с условием того, что погрешность решения имеет порядок 10).

Заключение

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

Список литературы:

1. Сарычева О.М. Численные методы. - Новосибирск, 1995. - 65с.

2. Бахвалов Н.С. Численные методы. Ч1.- М: Наука, 1975. - 632с., ил.

3. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах . - М: Наука, 1972. - 368с.

Размещено на Allbest.ru