Отчёты по лабораторным работам




Скачать 454.75 Kb.
НазваниеОтчёты по лабораторным работам
страница1/7
Дата публикации15.03.2013
Размер454.75 Kb.
ТипЛабораторная работа
vbibl.ru > Информатика > Лабораторная работа
  1   2   3   4   5   6   7
Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Отчёты по лабораторным работам

по курсу «Вычислительные методы алгебры»

Выполнил:

ст.гр. 052003

Смоляков К.Ю.
Проверила:

Поддубная О.Н.

Минск, 2012

Лабораторная работа №2


«Численное решение систем линейных уравнений методом простых итераций и методом Зейделя»

Цели выполнения задания:

  • Изучить итерационные методы решения СЛАУ (метод простых итераций, метод Зейделя).

  • Составить алгоритм решения СЛАУ указанными методами, применимый для организации вычислений на ЭВМ.

  • Составить программу решения СЛАУ по разработанному алгоритму.

  • Численно решить тестовые примеры и проверить правильность работы программы. Сравнить трудоемкость решения методом простых итераций и методом Зейделя.


^ Краткие теоретические сведения.

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

^ Итерационные методы основаны на построении сходящейся к точном решению x рекуррентной последовательности.
Для решения СЛАУ методом простых итераций преобразуем систему от первоначальной формы Ax = b или

a11 x1 + a12 x2 + … + a1n xn = b1 ,

a21 x1 + a22 x2 + … + a2n xn = b2 ,

….. (2.1)

an1 x1 + an2 x2 + … + ann xn = bn

к виду

x = Bx + c. (2.2)

Здесь B – квадратная матрица с элементами bij (i, j = 1, 2, …, n), c – вектор-столбец с элементами ci (i = 1, 2, …, n).

В развернутой форме записи система (2.2) имеет следующий вид:

x1 = b11x1 + b12x2 + b13x3 + … + b1nxn + c1

x2 = b21x1 + b22x2 + b23x3 + … + b2nxn + c2

. . . . . . . . . . . . . . . . .

xn = bn1x1 + bn2x2 + bn3x3 + … + bnnxn + cn

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

Можно, например, преобразовать систему (2.1) следующим образом

x1 = (b1 - a11 x1 – a12 x2 - … - a1n xn) / a11 + x1,

x2 = (b2 - a21 x1 – a22 x2 - … - a2n xn) / a22 + x2,

…..

xn = (bn - an1 x1 – an2 x2 - … - ann xn) / ann + xn
если диагональные элементы матрицы А отличны от нуля.
Можно преобразовать систему (2.1) в эквивалентную ей систему

x = (E-A)x+b.

Задав произвольным образом столбец начальных приближений х0 = (x10 , x20 , … , xn0 )T , подставим их в правые части системы (2.2) и вычислим новые приближения x1 = (x11 , x21 , … , xn1 )T , которые опять подставим в систему (2.2) и т.д. Таким образом, организуется итерационный процесс

xk = Bxk-1 + c , k = 1,2, …. ,. Известно, что система (2.1) имеет единственное решение х* и последовательность {xk} сходится к этому решению со скоростью геометрической прогрессии, если || B || < 1 в любой матричной норме. Т.е.

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



^ Метод Зейделя. Метод Зейделя является модификацией метода простых итераций. Суть его состоит в том, что при вычислении следующего : 2 в формуле xk = Bxk-1 + c , k = 1,2, …. используются вместо уже вычисленные ранее , т.е.

. (2.3)

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

Схема алгоритма аналогична схеме метода простых итераций.

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x1:

x1 = a11–1 (b1a12x2a13x3 – … – a1nxn),

из второго уравнения – неизвестное x2:

x2 = a21–1 (b2a22x2a23x3 – … – a2nxn),

и т. д. В результате получим систему

x1 = b12x2 + b13x3 + … + b1,n–1xn–1 + b1nxn+ c1 ,

x2 = b21x1 + b23x3 + … + b2,n–1xn–1 + b2nxn+ c2 ,

x3 = b31x1 + b32x2 + … + b3,n–1xn–1 + b3nxn+ c3 ,

. . . . . . . . . . . . . . . . . . . . . . .

xn = bn1x1 + bn2x2 + bn3x3 + … + bn,n–1xn–1 + cn ,

в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам

bij = –aij / aii, ci = bi / aii (i, j = 1, 2, …, n, j ≠ i) (2.4)

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

Введем нижнюю B1 (получается из B заменой нулями элементов стоявших на главной диагонали и выше ее) и верхнюю B2 (получается из B заменой нулями элементов стоявших на главной диагонали и ниже ее) треугольные матрицы.

Заметим, что B = B1 + B2 и поэтому решение x исходной системы удовлетворяет равенству

x = B1x + B2 x + c (2.5)

Выберем начальное приближение x(0) = [x1(0), x2(0), …, xn(0)]T. Подставляя его в правую часть равенства при верхней треугольной матрице B2 и вычисляя полученное выражение, находим первое приближение

x(1) = B1x(0) + B2x(1) (2.6)

Подставляя приближение x(1), получим

x(2) = B1x(1) + B2x(2) (2.7)

Продолжая этот процесс далее, получим последовательность x(0), x(1), …, x(n), … приближений к вычисляемых по формуле

x(k+1) = B1(k+1) + B2(k) + c (2.8)

или в развернутой форме записи

x1(k+1) = b12x2(k) + b13x2(k) + … + b1nxn(k) + c1 ,

x2(k+1) = b21x1(k+1) + b23x3(k) + … + b2nxn(k) + c2 ,

x3(k+1) = b31x1(k+1) + b32x2(k+1) + … + b3nxn(k) + c3 ,

. . . . . . . . . . . . . . . . . . . . . . . . . .

xn(k+1) = bn1x1(k+1) + bn2x2(k+1) + bn3x3(k+1) + … + cn .

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

xi(k+1) = xi(k)aii–1(∑j=1i–1 aijxj(k+1) + ∑j=1n aijxi(k)bi). (2.9)

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

aii>ai1+ ……..+ain для всех i=1,…n,

или ajj>a1j+…….+anj для всех j=1,….,n.

Методы простой итерации и Зейделя сходятся примерно так же, как геометрическая прогрессия со знаменателем || B ||
^ Исходный код программы:

function [converge, X, iterations, closure] = SimpleIterationsMethod( A, b, eps, max )

%Solves the system of linear equations

B = zeros(size(A,1), size(A, 2));

c = b;

for i = 1 : size(A, 1)

c(i) = c(i) / A(i,i);

for j = 1 : size(A, 2)

if (i == j)

B(i, j) = 0;

else

B(i, j) = - A(i, j) / A(i, i);

end;

end;

end;

converge = true;

k = 1;

x0 = c;

xk = B * x0 + c;

norm_no = 1;

coef = 0;

if (norm(B, norm_no) > 1)

norm_no = 2;

if (norm(B, norm_no) > 1)

norm_no = Inf;

if (norm(B, norm_no) > 1)

norm_no = 1;

coef = 1;

end;

end;

end;

if (coef ~= 1)

coef = norm(B, norm_no) / (1 - norm(B, norm_no)) ;

end;

while (norm(xk - x0, norm_no) * coef >= eps)

x0 = xk;

xk = B * x0 + c;

k = k + 1;

if (k == max && coef == 1)

converge = false;

break;

end;

end

X = xk;

iterations = k;

closure = A * X - b;

end

function [ x, best_k, best_t, closure, converge ] = SimpleIterationsMethod2( A, b, eps, max_iterations, t_min, t_max)

%Solves the system of linear equations

N = size(A, 1);

best_t = 0;

best_k =Inf;

step = (t_max - t_min) / 1000;

fileId = fopen('report.txt', 'w');

for t = t_min : step : t_max

if (t == 0)

continue;

end;

B = eye(N) - t * A;

c = t * b;

norm_no = 1;

coef = 0;

if (norm(B, norm_no) > 1)

norm_no = 2;

if (norm(B, norm_no) > 1)

norm_no = Inf;

if (norm(B, norm_no) > 1)

norm_no = 1;

coef = 1;

end;

end;

end;

if (coef ~= 1)

coef = norm(B, norm_no) / (1 - norm(B, norm_no)) ;

end;

k = 1;

x0 = c;

xk = B * x0 + c;

converge = true;

while (norm(xk - x0, norm_no) * coef >= eps )

x0 = xk;

xk = B * x0 + c;

k = k + 1;

for i = 1 : size(xk)

if (isnan(xk(i)) || isinf(xk(i)))

converge = false;

break;

end;

end;

if (converge == false || (coef == 1 && k == max_iterations))

converge = false;

break;

end;

end;

fprintf(fileId, '\tX when t = %.4f, k = %d\n', t, k);

if (converge)

fprintf(fileId, '%.4f\n', xk);

else

fprintf(fileId, 'Converge == false');

end;

fprintf(fileId, '\n\n');

if (k < best_k && converge == true)

best_k = k;

best_t = t;

x = xk;

end;

end;

converge = best_k < Inf;

if (converge)

closure = A * x - b;

else

closure = Inf;

x = Inf;

end;

fclose(fileId);

end
function [converge, X, iterations, U] = ZeidelMethod( A, b, eps, max )

B = zeros(size(A,1), size(A, 2));

c = b;

for i = 1 : size(A, 1)

c(i) = c(i) / A(i,i);

for j = 1 : size(A, 2)

if (i == j)

B(i, j) = 0;

else

B(i, j) = - A(i, j) / A(i, i);

end;

end;

end;

useMax = false;

norm_no = 1;

if (norm(B, norm_no) > 1)

norm_no = Inf;

if (norm(B, norm_no) > 1)

useMax = true;

end;

end;

n = norm(B, norm_no);

x = c;

k = 0;

while (true)

for i = 1 : size(A, 1)

var = 0;

for j = 1 : size(A, 2)

if (j ~= i)

var = var + B(i, j) * x(j);

end;

end;

x(i) = (c(i) + var) ;

end;

k = k + 1;

if (norm(A*x - b, norm_no) <= eps)

break;

end;

if (useMax && k >= max)

break;

end;

end;

X = x;

iterations = k;

if (useMax && k == max)

converge = false;

U = Inf;

else

converge = true;

U = A*X - b;

end;

end
  1   2   3   4   5   6   7

Добавить документ в свой блог или на сайт

Похожие:

Отчёты по лабораторным работам iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Отчёты по лабораторным работам iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Отчёты по лабораторным работам iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Отчёты по лабораторным работам iconСправочник по персоналу фио
Задание к лабораторным работам по дисциплине «Налоги и налогообложение» студентов специальности «Финансы и кредит»

Отчёты по лабораторным работам iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Отчёты по лабораторным работам iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Отчёты по лабораторным работам iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Отчёты по лабораторным работам iconКвалификационных работ
Вкр), курсовых работ (проектов), рефератов, контрольных работ, отчетов по практикам, лабораторным работам, выполняемых студентами...

Отчёты по лабораторным работам iconМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по выбору рациональных структур...

Отчёты по лабораторным работам iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница