close

Вход

Забыли?

вход по аккаунту

?

Отчет ЛР№2 Юля

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет»
Кафедра АСОИУ
ОТЧЕТ
по лабораторной работе №2
на тему «Решение систем линейных алгебраических уравнений итерационными
методами»
по дисциплине «Вычислительная математика»
Вариант №6
Выполнил:
студентка гр.Б03-782-1
Ю.С. Вотинцева
Проверил:
ст. преподаватель кафедры АСОИУ
А.А. Коробейников
Ижевск 2012
1 ПОСТАНОВКА ЗАДАЧИ
Написать программу, реализующую алгоритмы:
а) метода простых итераций;
б) метода Зейделя.
с точностью  = 10-12.
В программе требуется:
1) предусмотреть приведение СЛАУ к виду, пригодному для итераций;
2) организовать проверку условия сходимости методов;
3) выбрать начальное приближение;
4) сделать априорную оценку количества шагов и подсчитать реальное количество шагов
для достижения заданной точности указанных методов;
5) подсчитать апостериорные оценки методов.
Провести сравнительный анализ метода простых итераций и метода Зейделя.
2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
2.1 Итерационные методы решения СЛАУ
Пусть дана система n линейных уравнений с n неизвестными:
 a11x1  a12 x2  ...  a1n xn  b1 ,
a x  a x  ...  a x  b ,
 21 1
22 2
2n n
2

...

an1 x1  an2 x2  ...  ann xn  bn .
(1)
Запишем систему (1) в матричном виде:
A x = b,
(2)
Преобразуем систему (2) тем или иным способом (таких способов существует
множество; некоторые из них будут рассмотрены ниже) к эквивалентной ей системе вида:
x = x + ,
где
(3)
x – тот же вектор неизвестных, ,  - некоторые новые матрица и вектор
соответственно.
Эта система называется приведенной к нормальному виду. Она пригодна для
итерационного процесса.
2.2 Методы простых итераций (МПИ) решения СЛАУ
Пусть система линейных алгебраических уравнений (2) приведена к нормальному
виду (3)
тем или иным способом. Решим ее методом простых итераций. Используя
систему (3), можно определить последовательность приближений x(k) к неподвижной
точке x* рекуррентным равенством
x(k+1)=  x(k)+,
(4)
где k =0,1,2,….
Итерационный процесс (4), начинающийся с некоторого вектора
x(0) =( x
( 0)
1
,…, x (n0) )Т, будем называть методом простых итераций (МПИ).
Приближения к решению СЛАУ методом простых итераций могут быть записаны в
виде следующей системы равенств:
x1( k 1)  11x1( k )  12 x2( k )  ...  1n xn( k )  1

x2( k 1)   21x1( k )   22 x2( k )  ...   2n xn( k )   2

...
 (k )
(k )
(k )
(k )
xn1   n1 x1   n2 x2  ...   nn xn   n ,
где k = 0,1,2, …
(5)
Выбор начального приближения
Сходимость МПИ гарантирована при любом начальном векторе x(0). Очевидно, что
итераций потребуется меньше, если x(0) ближе к решению x*. Если нет никакой
информации о грубом решении задачи (3) или решении близкой задачи, то за x (0) обычно
принимают вектор  свободных членов системы (3).
Способы приведения СЛАУ к нормальному виду
Для решения СЛАУ итерационными методами систему (2) нужно привести к
эквивалентной ей системе (3), которая называется системой, приведенной к нормальному
виду каким-либо способом. Рассмотрим их.
1. Если в матрице коэффициентов  наблюдается диагональное преобладание, т. е.
|a | | a
ij
ii
|,
j#i,
i =1,2,…n,
j 1
то систему (3) можно получить, разделив уравнения системы на соответствующие
диагональные элементы и выразив x1 через первое уравнение системы, x2 – через второе и
т.д. В результате получим:

 0
 a12  a12

a11
a11

a21
0
 a23
    a22
a22
 ...
...
...
 an1
 an 2  a n 3
 
ann
ann
 ann

a1,n1
 a1n 
a11
a11 
a
a 
...  2,n1  2,n 
a22
a22 
...
...
... 

a
...  n,n1
0 
ann

... 
- новая матрица коэффициентов
T


   b1 ; b2 ;... bn  - новый вектор свободных членов
 a11 a22 ann 
2. Иногда выгоднее приводить систему (2) к виду (3) так, чтобы коэффициенты ii
не были равны нулю.
Вообще, имея систему
n
a
ij
i 1
x j  bi , i = 1, 2, … n,
можно положить
aii  aii(1)  aii(2) ,
где aii(1) # 0. Тогда исходная система эквивалентна нормальной системе:
xi   i   ij x j
, i =1, 2, … n,
j 1
( 2)
aij
где  i  b(1i ) ;  ii   aii(1) ;  ij   ij при i # j
aii
aii
aii
Теорема 1. Пусть ||||  q < 1. Тогда при любом начальном векторе x(0) МПИ сходится к
единственному решению x* и при всех k  N справедливы оценки погрешности:
1) || х *-х(k) ||
q
||х(k)-х(k-1) || - апостериорная
1 q
(6)
qk
2) || х -х ||
||х(1)-х(0) || - априорная
1 q
*
(k)
(7)
Здесь обозначение ||.|| используется для матричных и векторных норм, согласованных
между собой, т.е. таких, что ||Ах||  ||А||||х||.
В качестве матричных норм может быть использована одна из следующих:
||||1 =
n
max  
i 1
j
|||| =
n
max  
i 1
i

n
f=
 1 (норма – сумма), j = 1,2…n
ij
n
 
i 1 j 1
2
1
ij
1
ij
(норма – максимум), I = 1,2…n
(норма Фробениуса)
В качестве векторных норм может быть использована одна из следующих:


 max  i
i1,...n
n
x
2
i 1
2
i
n
 1 x
i 1
- (норма-максимум)
- (евклидова норма)
- (норма-сумма)
i
Согласованными между собой матричными и векторными нормами являются: 
и  1; 
2
и  2; 

и 

.
1
Априорная оценка позволяет подсчитывать заранее число итераций k, достаточное
для получения решения х* с заданной точностью  при выбранном начальном векторе х(0).
Для этого нужно найти наименьшее целое решение неравенства
qk
||х(1)-х(0) || 
1 q
относительно переменной k.
Апостериорной оценкой пользуются непосредственно в процессе вычислений и
применяют для останова процесса итераций при выполнении неравенства:
||х(k)-х(k-1) || 
1 q

q
2.3. Метод Зейделя
Метод Зейделя представляет собой модификацию МПИ (5) решения СЛАУ, при
котором для подсчета i-й компоненты (k+1)-го приближения используются уже
найденные на этом, т.е. (k+1)-м шаге, новые значения первых (i-1) компонент. Т.е., если
система (1) тем или иным способом сведена к системе (3) с матрицей коэффициентов  и
вектором свободных членов , то приближения к ее решению по методу Зейделя
определяются системой равенств:
 x1( k 1)  11x1( k )  12 x2( k )  ...  1n xn( k )  1 ,
 ( k 1)
( k 1)
(k )
(k )
 x2   21x1   22 x2  ...   2n xn   2 ,

...

xn( k 1)   n1 x1( k 1)   n2 x2( k 1)  ...   nn xn( k )   n ,
(8)
где k = 0, 1, 2, …;
xi(0) – компоненты выбранного начального вектора.
Теорема 1 о сходимости МПИ остается верной и для метода Зейделя. Выбор
начального приближения осуществляется по тому же принципу, что и в МПИ.
Документ
Категория
Математика
Просмотров
19
Размер файла
114 Кб
Теги
отчет, юля
1/--страниц
Пожаловаться на содержимое документа