Рефетека.ру / Математика

Контрольная работа: Точные методы численного решения систем линейных алгебраических уравнений

Министерство науки и образования Украины

Сумской государственный университет

Механико-математический факультет

Кафедра информатики


Точные методы численного решения систем линейных алгебраических уравнений”


Сумы 2006

Содержание


Постановка задачи

1. Введение

2. Точные методы решения СЛАУ

3. Практическая реализация метода Халецкого

3.1 Программа на языке Pascal

3.2 Решение в Excel

Заключение

Литература

Приложение


Постановка задачи


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


1. Введение


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

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

Пример системы линейных уравнений:


Точные методы численного решения систем линейных алгебраических уравнений


Или в матричном виде: Точные методы численного решения систем линейных алгебраических уравнений,


где Точные методы численного решения систем линейных алгебраических уравненийматрица коэффициентов системы;


Точные методы численного решения систем линейных алгебраических уравнений - вектор неизвестных; Точные методы численного решения систем линейных алгебраических уравнений- вектор свободных членов.

2. Точные методы решения СЛАУ


Метод главных элементов.

Пусть дана система линейных алгебраических уравнений. Рассмотрим расширенную матрицу, состоящую из коэффициентов системы a[i,j] и свободных членов b[i]. Метод главных элементов - это обобщение метода исключения переменных (метода Гаусса). Обозначим матрицу, состоящую из коэффициентов при неизвестных и столбца свободных членов исходной системы за M.

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

Вычисляются множители:


Точные методы численного решения систем линейных алгебраических уравнений


Далее производим следующие преобразования: к каждой неглавной строке прибавим главную строку, умноженную на соответствующий множитель Точные методы численного решения систем линейных алгебраических уравненийдля этой строки. В результате мы получим матрицу, у которой q-й столбец состоит из нулей. Отбросим этот столбец и главную p-ю строку, получим новую матрицу Точные методы численного решения систем линейных алгебраических уравненийс меньшим на единицу числом строк и столбцов. Над матрицей Точные методы численного решения систем линейных алгебраических уравненийповторяем те же операции, после чего получаем матрицу Точные методы численного решения систем линейных алгебраических уравненийи т.д. Таким образом, мы построим последовательность матриц


Точные методы численного решения систем линейных алгебраических уравнений


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

Заметим, что метод Гаусса является частным случаем, метода главных элементов, а схема метода Гаусса получается, если за главный элемент всегда выбирать левый верхний элемент соответствующей матрицы. Запрограммировать метод главных элементов непросто, поэтому чтобы уменьшить вычислительную погрешность, применяют метод Гаусса с выбором главного элемента. Необходимое условие применения метода главных элементов: определитель системы не равен нулю.

Метод квадратных корней

Метод квадратных корней разработан для решения линейных систем с симметричной матрицей коэффициентов. Пусть дана линейная система


Ax=b,


где Точные методы численного решения систем линейных алгебраических уравненийили Точные методы численного решения систем линейных алгебраических уравнений(симметрическая матрица).

Симметричную матрицу можно представить в виде произведения двух транспонированных между собой треугольных матриц

A=T'*T,


Точные методы численного решения систем линейных алгебраических уравнений


Перемножим матрицы T' и T. Из T' i-ю строку из T j-тый столбец, получим следующие уравнения:


Точные методы численного решения систем линейных алгебраических уравнений


Последовательно находим:


Точные методы численного решения систем линейных алгебраических уравнений


Точные методы численного решения систем линейных алгебраических уравнений


После подстановки в систему, последняя распадается на две системы с треугольными матрицами.


Точные методы численного решения систем линейных алгебраических уравнений


Решим систему T'*y=b. Запишем её в развёрнутом виде:


Точные методы численного решения систем линейных алгебраических уравнений


Отсюда последовательно находим

Точные методы численного решения систем линейных алгебраических уравнений


Решаем систему T*x=y, записав её в развёрнутом виде:


Точные методы численного решения систем линейных алгебраических уравнений


Решение имеет вид


Точные методы численного решения систем линейных алгебраических уравнений


Прямым ходом с помощью формул вычисляются t[i,j] и y[i], обратным ходом по формуле находятся x[i].Текущий контроль прямого хода осуществляется с помощью так называемых "контрольных сумм", которые представляют собой сумму элементов строк матрицы исходной системы, включая свободные члены. Если над контрольными суммами в каждой строке проделывать те же операции, что и над остальными элементами этой строки, то при отсутствии ошибок в вычислениях сумма преобразованных элементов равна преобразованной сумме. Обратный ход контролируется следующим образом: если в формулах для определения Точные методы численного решения систем линейных алгебраических уравненийвместо столбца свободных членов взять соответствующие элементы из столбца контрольных сумм, то получим новые неизвестные, которые обозначимТочные методы численного решения систем линейных алгебраических уравнений'.

При отсутствии ошибок Точные методы численного решения систем линейных алгебраических уравнений'-Точные методы численного решения систем линейных алгебраических уравнений=1.

Метод Халецкого

Запишем систему линейных уравнений в матричном виде:


Точные методы численного решения систем линейных алгебраических уравнений,


где A=[aij] – квадратная матрица порядка n и


Точные методы численного решения систем линейных алгебраических уравнений, Точные методы численного решения систем линейных алгебраических уравнений - векторы-столбцы.


Представим матрицу A в виде произведения нижней треугольной матрицы B=[bij] и верхней треугольной матрицы C=[cij] с единичной диагональю Точные методы численного решения систем линейных алгебраических уравнений, где


Точные методы численного решения систем линейных алгебраических уравнений и Точные методы численного решения систем линейных алгебраических уравнений.


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


Точные методы численного решения систем линейных алгебраических уравнений и Точные методы численного решения систем линейных алгебраических уравнений


Отсюда искомый вектор x может быть вычислен из уравнений Точные методы численного решения систем линейных алгебраических уравнений и Точные методы численного решения систем линейных алгебраических уравнений.

Так как матрицы B и C – треугольные, то системы легко решаются:


Точные методы численного решения систем линейных алгебраических уравнений и Точные методы численного решения систем линейных алгебраических уравнений


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


Точные методы численного решения систем линейных алгебраических уравнений


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


Точные методы численного решения систем линейных алгебраических уравнений


Решение.

В первый раздел таблицы впишем матрицу коэффициентов системы, ее свободные члены и контрольные суммы. Далее так как Точные методы численного решения систем линейных алгебраических уравнений Точные методы численного решения систем линейных алгебраических уравнений, то первый столбец из раздела 1 переносится в первый столбец раздела II. Чтобы получить первую строку раздела II, делим все элементы первой строки раздела I на элементТочные методы численного решения систем линейных алгебраических уравнений, в нашем случае на 3.

Имеем:

Точные методы численного решения систем линейных алгебраических уравнений;

Точные методы численного решения систем линейных алгебраических уравнений;

Точные методы численного решения систем линейных алгебраических уравнений;

Точные методы численного решения систем линейных алгебраических уравнений;

Точные методы численного решения систем линейных алгебраических уравнений.


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


Точные методы численного решения систем линейных алгебраических уравнений;

Точные методы численного решения систем линейных алгебраических уравнений;

Точные методы численного решения систем линейных алгебраических уравнений.


Далее определяя по формулам, заполняем вторую сетку для раздела II:


Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений


Затем переходим к третьему столбцу, вычисляя его элементы Точные методы численного решения систем линейных алгебраических уравнений и Точные методы численного решения систем линейных алгебраических уравнений по формулам и т.д., пока не будет заполнена вся таблица раздела II. Таким образом, заполнение раздела II происходит способом “елочки”: столбец - строка, столбец - строка и т.д.

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

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


Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

I

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

3 1 -1 2 6 11
I

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

-5 1 3 -4 -12 -17
I

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

2 0 1 -1 1 3
I

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

1 -5 3 -3 3 -1
II

Точные методы численного решения систем линейных алгебраических уравнений│1

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

3│1 0.333333 -0.333333 0.666667 2 3.666667
II

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений│1

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

-5 2.666667│1 0.5 -0.25 -0.75 0.5
II

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений│1

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

2 -0.666667 2│1 -1.25 -1.75 -2
II

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений│1

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

1 -5.333333 6 2.5│1 3 4
III

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

2 1
III

Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений

-0.75 -1
III y3

Точные методы численного решения систем линейных алгебраических уравнений

-1.75 2
III y4

Точные методы численного решения систем линейных алгебраических уравнений

3 3

3. Практическая реализация метода Халецкого


3.1 Программа на языке Pascal


program kursovaya;

uses crt;

const sizemat=10;

type mattype=array[1..sizemat,1..sizemat] of double;

mattype1=array[1..sizemat] of double;

{Процедура для вывода матрицы на экран}

procedure writemat (var a:mattype; n,m:byte);

var i,j:byte;

begin

writeln;

for i:=1 to n do

begin

for j:=1 to m do

write(a[i,j]:7:3,' ');

writeln

end;

end;

{Процедура для ввода значений элементов матрицы}

procedure inputmat (var a:mattype;var d:mattype1; var n:byte);

var i,j:byte;

begin

writeln;

write ('Введите размер матрицы = ');

readln(n);

writeln;

writeln('Введите матрицу:');

writeln;

for i:=1 to n do

for j:=1 to n do

read (a[i,j]);

writeln;

writeln('Введите свободные коэффициенты:');

writeln;

for i:=1 to n do

readln(d[i]);

writeln;

end;

{Процедура получения двух треугольных матриц, произведение которых равно исходной матрице}

procedure getBnC(var a,b,c:mattype; n:byte);

var k,i,a1,j:byte;

begin

for k:=1 to n do

for i:=1 to n do

begin

if k=i then c[k,i]:=1

else c[k,i]:=0;

b[k,i]:=0;

end;

for a1:=1 to n do

begin

if a1=1 then

begin

for i:=1 to n do

b[i,1]:=a[i,1];

for i:=2 to n do

c[1,i]:=a[1,i]/b[1,1];

end

else

begin

k:=a1;

for i:=a1 to n do

begin

b[i,k]:=a[i,k];

for j:=1 to k-1 do

b[i,k]:=b[i,k]-b[i,j]*c[j,k];

end;

i:=a1;

for k:=i+1 to n do

begin

c[i,k]:=a[i,k];

for j:=1 to i-1 do

c[i,k]:=c[i,k]-b[i,j]*c[j,k];

c[i,k]:=c[i,k]/b[i,i];

end;

end;

end;

end;

procedure otvet(var b,c:mattype; d:mattype1; n:byte);

var x,y,s:mattype1;

i,j,k:byte;

w,q:double;

y1,x1:mattype;

begin

for i:=1 to n do

if i=1 then y[i]:=d[i]/b[i,i]

else

begin

w:=0;

for k:=1 to i-1 do

begin

y1[i,k]:=w+b[i,k]*y[k];

w:=y1[i,k];

end;

y[i]:=(d[i]-w)/b[i,i];

end;

for i:=n downto 1 do

if i=n then x[i]:=y[i]

else

begin

q:=0;

for k:=i+1 to n do

begin

x1[i,k]:=q+c[i,k]*x[k];

q:=x1[i,k];

end;

x[i]:=y[i]-q;

end;

writeln;

writeln('Ответ X:');

writeln;

for i:=1 to n do

writeln('x[',i,']= ',x[i]:1:4);

writeln;

end;

{Основная программа}

var a,a1,c,b:mattype;

d:mattype1;

n:byte;

begin

clrscr;

writeln ('Курсовая работа ');

InputMat(a,d,n); {Ввод матрицы A }

getBnC(a,b,c,n);{ Получение треугольных матриц B u C}

Writeln('Матрица B: ');

writemat(b,n,n);

readln;

Writeln('Матрица C: ');

writemat(c,n,n);

otvet(b,c,d,n);

readln;

end.


3.2 Решение в Excel


Точные методы численного решения систем линейных алгебраических уравнений

Точные методы численного решения систем линейных алгебраических уравнений


Заключение


Первым из алгоритмов, посвященным большому разделу решения систем линейных уравнений, представляем алгоритм Халейкого. Это фактически метод решения систем общего вида, конкурирующий по быстродействию с общеизвестным методом Гаусса-Жордана, но позволяющий более эффективно использовать решение.

Если мы можем разложить матрицу линейной системы A в произведение A=L*U(B*C), где L(B) - нижняя, а U(C) - верхняя треугольные матрицы, то решение системы уравнений с произвольной правой частью производится весьма просто, применением двух обратных подстановок. Более того, в отличие от известного метода Гаусса-Жордана, разложенная матрица позволяет быстро решать серии линейных уравнений с различными правыми частями при одной и той же матрице.

Метод Халецкого позволяет провести LU-декомпозицию матрицы примерно за то же число операций, что и "прямая" часть метода Гаусса-Жордана. Итоговые коэффициенты двух треугольных матриц упаковываются в матрицу того же размера, что и A, и на том же месте в памяти. При этом верхняя матрица U размещается в наддиагональной части и на диагонали; нижняя L в поддиагональной части, а диагональные элементы L считаются все равными 1 (без ограничения общности) и не выводятся.

Метод Халецкого исключительно является точным методом, при этом предполагалось, что арифметические операции выполняются над точными числами. Если же метод реализуется на ЭВМ, то появляется вычислительная погрешность, заметим, что даже результаты точных методов являются приближенными из-за неизбежных округлений. Для итерационных процессов также добавляется погрешность метода.

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


Литература


Б.П. Демидович и И.А. Марон. “Основы вычислительной математики”, Москва, 1963г.

Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. “Численные методы”, Москва, 1987г.

Ю.П. Боглаев. “Вычислительная математика и программирование”, Москва, 1990г.

Приложение


Результаты работы программы:

Точные методы численного решения систем линейных алгебраических уравнений

Похожие работы:

  1. • Расчет жесткого стержня
  2. • Решение произвольных систем линейных уравнений
  3. • Решение систем линейных алгебраических уравнений методом ...
  4. • Решение систем линейных алгебраических уравнений
  5. • Численные методы решения систем линейных уравнений
  6. • ЭВМ с использованием математического пакета ...
  7. • Методы решения систем линейных уравнений
  8. • Разработка программы решения системы линейных ...
  9. • Поиск решений системы линейных уравнений методом ...
  10. • Численное решение системы линейных уравнений с ...
  11. • Геофизический "диалект" языка математики
  12. • Решение систем линейных дифференциальных уравнений ...
  13. • Численное решение системы линейных алгебраических ...
  14. • Точные методы решения систем линейных алгебраических ...
  15. • Методы решения алгебраических уравнений
  16. • Метод Гаусса для решения систем линейных уравнений
  17. • Поиски более рационального способа решения систем линейных ...
  18. • Прямые методы решения систем линейных алгебраических ...
  19. • Итерационные методы решения систем линейных ...
Рефетека ру refoteka@gmail.com