3.3. Алгоритмы основных (простейших) итерационных методов
1) Метод релаксации (ослабления). Алгоритм метода релаксации задается формулой
или (см. (28))
Метод
релаксации сходится для симметричной
положительно определенной матрицы
при
.
2) Метод Якоби. Алгоритм метода Якоби задается формулой
или (см. (28))
Метод Якоби сходится, если матрица имеет преобладающую главную диагональ:
3) Метод Зейделя. Представим матрицу в виде
где
Алгоритм метода Зейделя записывается в виде (см. (29)):
или (см. (28))
Метод
Зейделя неявный, но матрица
легко
обратима. Отсюда получаем вычислительные
формулы алгоритма метода Зейделя:
По
теореме 2 метод Зейделя сходится тогда
и только тогда, когда все собственные
значения матрицы
по модулю
меньше единицы. Нетрудно проверить, что
эти собственные значения являются
корнями уравнения
Метод Зейделя сходится, если матрица имеет преобладающую главную диагональ.
Если матрица
симметричная и положительно определенная,
то метод Зейделя является сходящимся.
Следовательно, метод Зейделя всегда
сходится для эквивалентной системы
4) Метод верхней релаксации. В обозначениях (29) алгоритм метода верхней релаксации задается формулой (см. (28))
или (см. (27))
При
отсюда
получаем метод Зейделя.
Если матрица
симметричная и положительно определенная,
то метод верхней релаксации является
сходящимся при
.
4. Итерационное уточнение решения
Пусть
- реально вычисленное (любым способом,
например, методом Гаусса) решение системы
(1). Запишем точное решение
системы (1) в виде
Подставив это выражение в (1), получим
где
Вектор
называется
невязкой. Теперь, решая систему (30),
найдем поправку
.
Следующее приближение к точному решению
системы (1) получается как
,
где
-
реально вычисленное решение системы
(30). Затем вычисляем невязку
и
вторую поправку к точному решению
как
решение системы (30) с правой частью
Вторым приближением к решению будет
вектор
и так далее.
Будем
считать, что численный метод решения
системы (30) и применяемая машинная
арифметика вычисления невязки таковы,
что реальная поправка
удовлетворяет
условию
где
заметно
меньше единицы. Основная трудность в
удовлетворении этого условия связана
со способом
вычисления невязки. Если
достаточно
близко к точному решению, то невязка
мала и ее вычисление приводит к большим
относительным ошибкам. Кроме того,
малость невязки может привести к
значительной потере точности при
вычислении поправки
(вычисления вблизи машинного нуля).
Поэтому обычно поступают следующим
образом:
Вычисляют невязку с удвоенной точностью.
Нормируют невязку.
Решают систему (30).
Умножают вычисленную поправку на величину обратную нормирующему множителю.
Процесс уточнения решения тем эффективнее, чем меньше . Обычно достаточно провести 2-3 итерации, чтобы достичь нужной точности.
Замечание 12. При последовательном выполнении процесса уточнения решения 1)-4) нет никаких оснований ожидать существенного уменьшения норм невязок. Более того, нормы невязок на некоторых шагах могут даже несколько увеличиться. Несмотря на это точность последовательных приближений повышается.
Описанный процесс уточнения связан с устранением влияния обусловленности матрицы исходной системы на погрешность в решении.
Внимание! Более подробное изложение рассмотренных и других методов решения систем линейных уравнений можно найти в [3], [4] и на сайте: http://www.srcc.msu.su/num_anal (см. раздел «Учебно-методические материалы»).
Задание.
Найдите решение системы линейных
уравнений с точностью
методами Гаусса, простой итерации и
Зейделя.
Варианты заданий
Номер |
Матрица |
Вектор |
1 |
27.70153 2.71425 -0.85915 0.99784 -0.78454 -1.85121 34.29314 2.11113 4.53818 -0.66302 -0.18283 1.68413 24.80947 3.07213 3.91096 -3.82808 3.08101 2.52143 31.08655 1.41026 -1.80561 3.17782 2.32840 -2.29968 34.34837 |
2.06829 0.11903 4.44773 -3.16207 0.84720 |
2 |
28.07253 2.75060 -0.87066 1.01121 -0.79505 -1.87601 34.75242 2.13941 4.59896 -0.67190 -0.18528 1.70669 25.14174 3.11327 3.96334 -3.87935 3.12227 2.55520 31.50288 1.42915 -1.82980 3.22038 2.35959 -2.33048 34.80840 |
4.50730 -3.20442 0.85854 2.09599 0.12062 |
3 |
28.44353 2.78695 -0.88216 1.02457 -0.80556 -1.90080 35.21171 2.16768 4.65974 -0.68078 -0.18773 1.72924 25.47401 3.15442 4.01572 -3.93062 3.16353 2.58897 31.91922 1.44804 -1.85398 3.26294 2.39077 -2.36128 35.26842 |
2.12369 0.12222 4.56687 -3.24677 0.86989 |
4 |
28.81453 2.82330 -0.89367 1.03793 -0.81607 -1.92559 35.67099 2.19596 4.72052 -0.68966 -0.19017 1.75180 25.80628 3.19556 4.06810 -3.98189 3.20480 2.62274 32.33556 1.46693 -1.87816 3.30550 2.42195 -2.39208 35.72844 |
2.15139 0.12381 4.62644 -3.28912 0.88124 |
5 |
29.55654 2.89600 -0.91668 1.06466 -0.83708 -1.97518 36.58956 2.25250 4.84208 -0.70742 -0.19507 1.79691 26.47082 3.27785 4.17286 -4.08443 3.28733 2.69027 33.16823 1.50470 -1.92653 3.39062 2.48432 -2.45368 36.64849 |
2.20679 0.12700 4.74557 -3.37381 0.90393 |
6 |
29.92754 2.93236 -0.92819 1.07803 -0.84759 -1.99997 37.04884 2.28078 4.90286 -0.71630 -0.19752 1.81946 26.80309 3.31899 4.22524 4.13570 3.32859 2.72404 33.58457 1.52359 -1.95071 3.43318 2.51551 -2.48448 37.10851 |
2.23449 0.12859 -4.80514 -3.41616 0.91527 |
7 |
30.29854 2.96871 -0.93970 1.09139 -0.85809 -2.02477 37.50812 2.30905 4.96364 -0.72518 -0.19997 1.84202 27.13536 3.36014 4.27761 -4.18696 3.36985 2.75781 34.00091 1.54248 -1.97489 3.47574 2.54669 -2.51528 37.56853 |
2.26219 0.13019 4.86471 -3.45851 0.92662 |
8 |
30.66955 3.00506 -0.95120 1.10475 -0.86860 -2.04956 37.96740 2.33733 5.02442 -0.73406 -0.20242 1.86458 27.46763 3.40128 4.32999 -4.23823 3.41112 2.79158 34.41725 1.56136 -1.99907 3.51830 2.57787 -2.54608 38.02856 |
2.28989 0.13178 4.92428 -3.50086 0.93797 |
9 |
31.04055 3.04141 -0.96271 1.11812 -0.87911 -2.07435 38.42669 2.36560 5.08520 -0.74293 -0.20487 1.88713 27.79990 3.44243 4.38237 -4.28950 3.45238 2.82535 34.83359 1.58025 -2.02325 3.56086 2.60906 -2.57688 38.48858 |
2.31759 0.13338 4.98384 -3.54321 0.94931 |
10 |
17.26399 1.69156 -0.53544 0.62187 -0.48894 -1.15370 21.37197 1.31569 2.82826 -0.41320 -0.11394 1.04958 15.46162 1.91459 2.43737 -2.38572 1.92013 1.57139 19.37358 0.87890 -1.12528 1.98046 1.45109 -1.43320 21.40640 |
1.28899 0.07418 2.77189 -1.97065 0.52798 |
11 |
17.63499 1.72791 -0.54694 0.63523 -0.49945 -1.17850 21.83126 1.34396 2.88904 -0.42208 -0.11639 1.07213 15.79389 1.95574 2.48975 -2.43698 1.96139 1.60516 19.78992 0.89778 -1.14947 2.02302 1.48228 -1.46400 21.86642 |
1.31669 0.07577 2.83146 -2.01300 0.53933 |
12 |
18.00599 1.76426 -0.55845 0.64860 -0.50995 -1.20329 22.29054 1.37224 2.94982 -0.43096 -0.11884 1.09469 16.12616 1.99688 2.54213 -2.48825 2.00266 1.63893 20.20626 0.91667 -1.17365 2.06558 1.51346 -1.49480 22.32644
|
1.34439 0.07737 2.89103 -2.05534 0.55068 |
13 |
18.37699 1.80061 -0.56996 0.66196 -0.52046 -1.22808 22.74982 1.40051 3.01060 -0.43984 -0.12129 1.11724 16.45843 2.03803 2.59450 -2.53952 2.04392 1.67270 20.62259 0.93556 -1.19783 2.10814 1.54464 -1.52559 22.78647 |
1.37209 0.07896 2.95059 -2.09769 0.56202 |
14 |
18.74800 1.83696 -0.58146 0.67532 -0.53097 -1.25288 23.20911 1.42878 3.07138 -0.44872 -0.12374 1.13980 16.79070 2.07917 2.64688 -2.59079 2.08518 1.70647 21.03893 0.95445 -1.22201 2.15070 1.57583 -1.55639 23.24649 |
1.39979 0.08056 3.01016 -2.14004 0.57337 |
15 |
19.11900 1.87332 -0.59297 0.68869 -0.54147 -1.27767 23.66839 1.45706 3.13216 -0.45760 -0.12618 1.16235 17.12297 2.12032 2.69926 -2.64206 2.12645 1.74024 21.45527 0.97333 -1.24620 2.19326 1.60701 -1.58719 23.70651 |
1.42749 0.08215 3.06973 -2.18239 0.58472 |
16 |
19.49000 1.90967 -0.60447 0.70205 -0.55198 -1.30246 24.12767 1.48533 3.19294 -0.46648 -0.12863 1.18491 17.45524 2.16146 2.75164 -2.69333 2.16771 1.77400 21.87161 0.99222 -1.27038 2.23582 1.63820 -1.61799 24.16653 |
1.45519 0.08374 3.12930 -2.22474 0.59606 |
17 |
19.86100 1.94602 -0.61598 0.71542 -0.56249 -1.32725 24.58696 1.51361 3.25372 -0.47536 -0.13108 1.20746 17.78751 2.20260 2.80402 -2.74460 2.20897 1.80777 22.28794 1.01111 -1.29456 2.27838 1.66938 -1.64879 24.62656 |
1.48289 0.08534 3.18887 -2.26709 0.60741 |
18 |
22.70536 2.22471 -0.70420 0.81787 -0.64305 -1.51733 28.10813 1.73037 3.71969 -0.54344 -0.14985 1.38039 20.33491 2.51805 3.20559 -3.13766 2.52533 2.06667 25.47987 1.15591 -1.47996 2.60468 1.90846 -1.88492 28.15340 |
1.69526 0.09756 3.64555 -2.59177 0.69440 |
19 |
23.44736 2.29742 -0.72721 0.84460 -0.66406 -1.56692 29.02669 1.78692 3.84125 -0.56120 -0.15475 1.42550 20.99945 2.60034 3.31035 -3.24020 2.60785 2.13421 26.31254 1.19369 -1.52832 2.68980 1.97083 -1.94652 29.07344
|
1.75066 0.10075 3.76469 -2.67646 0.71709 |
20 |
23.81837 2.33377 -0.73872 0.85797 -0.67457 -1.59171 29.48598 1.81520 3.90203 -0.57008 -0.15720 1.44805 21.33172 2.64148 3.36273 -3.29147 2.64912 2.16798 26.72888 1.21258 -1.55251 2.73236 2.00201 -1.97732 29.53347 |
1.77836 0.10234 3.82426 -2.71881 0.72844 |
21 |
24.18937 2.37012 -0.75022 0.87133 -0.68507 -1.61651 29.94526 1.84347 3.96281 -0.57896 -0.15965 1.47061 21.66399 2.68262 3.41511 -3.34274 2.69038 2.20175 27.14522 1.23146 -1.57669 2.77492 2.03319 -2.00812 29.99349 |
1.80606 0.10394 3.88382 -2.76116 0.73978 |
22 |
24.56037 2.40647 -0.76173 0.88469 -0.69558 -1.64130 30.40454 1.87175 4.02359 -0.58784 -0.16210 1.49316 21.99626 2.72377 3.46749 -3.39400 2.73164 2.23552 27.56155 1.25035 -1.60087 2.81748 2.06438 -2.03892 30.45351 |
1.83376 0.10553 3.94339 -2.80351 0.75113 |
23 |
24.93137 2.44282 -0.77324 0.89806 -0.70609 -1.66609 30.86383 1.90002 4.08437 -0.59672 -0.16455 1.51572 22.32853 2.76491 3.51987 -3.44527 2.77291 2.26929 27.97789 1.26924 -1.62505 2.86004 2.09556 -2.06972 30.91354 |
1.86146 0.10713 4.00296 -2.84586 0.76248 |
24 |
25.30238 2.47917 -0.78474 0.91142 -0.71660 -1.69089 31.32311 1.92829 4.14514 -0.60560 -0.16699 1.53827 22.66080 2.80606 3.57224 -3.49654 2.81417 2.30305 28.39423 1.28813 -1.64923 2.90260 2.12675 -2.10052 31.37356 |
1.88916 0.10872 4.06253 -2.88821 0.77382 |
25 |
25.57444 2.50583 -0.79318 0.92122 -0.72430 -1.70907 31.65992 1.94903 4.18972 -0.61211 -0.16879 1.55482 22.90446 2.83623 3.61066 -3.53414 2.84443 2.32782 28.69954 1.30198 -1.66697 2.93381 2.14961 -2.12310 31.71091 |
1.90947 0.10989 4.10621 -2.91927 0.78214 |
26 |
25.94545 2.54218 -0.80469 0.93459 -0.73481 -1.73386 32.11920 1.97730 4.25050 -0.62099 -0.17124 1.57737 23.23673 2.87738 3.66303 -3.58541 2.88569 2.36159 29.11588 1.32086 -1.69115 2.97637 2.18080 -2.15390 32.17093
|
1.93717 0.11148 4.16578 -2.96162 0.79349 |
27 |
26.31645 2.57853 -0.81619 0.94795 -0.74532 -1.75865 32.57848 2.00558 4.31127 -0.62987 -0.17369 1.59993 23.56900 2.91852 3.71541 -3.63668 2.92696 2.39536 29.53222 1.33975 -1.71533 3.01893 2.21198 -2.18470 32.63095 |
1.96487 0.11308 4.22535 -3.00396 0.80484 |
28 |
26.68745 2.61489 -0.82770 0.96131 -0.75582 -1.78345 33.03777 2.03385 4.37205 -0.63875 -0.17614 1.62248 23.90127 2.95966 3.76779 -3.68795 2.96822 2.42913 29.94856 1.35864 1.73952 3.06149 2.24317 -2.21550 33.09098 |
1.99257 -04.2849 -1.11467 3.04631 0.81618 |
29 |
26.98425 2.64397 -0.83691 0.97200 -0.76423 -1.80328 33.40519 2.05647 4.42068 -0.64585 -0.17809 1.64053 24.16708 2.99258 3.80970 -3.72896 3.00123 2.45614 30.28163 1.37375 -1.75886 3.09554 2.26811 -2.24014 33.45900 |
2.01473 0.11595 4.33257 -3.08019 0.82526 |
30 |
27.35526 2.68032 -0.84841 0.98537 -0.77474 -1.82807 33.86448 2.08474 4.48146 -0.65473 -0.18054 1.66308 24.49935 3.03372 3.86207 -3.78023 3.04250 2.48991 30.69796 1.39264 -1.78304 3.13810 2.29930 -2.27094 33.91902 |
2.04243 0.11754 4.39214 -3.12254 0.83661 |
31 |
27.72626 2.71667 -0.85992 0.99873 -0.78524 -1.85287 34.32376 2.11302 4.54224 -0.66361 -0.18299 1.68564 24.83162 3.07487 3.91445 -3.83150 3.08376 2.52368 31.11430 1.41152 -1.80723 3.18066 2.33048 -2.30174 34.37904 |
2.07013 0.11913 4.45170 -3.16489 0.84795 |
32 |
28.09726 2.75302 -0.87143 1.01210 -0.79575 -1.87766 34.78304 2.14129 4.60302 -0.67249 -0.18544 1.70819 25.16389 3.11601 3.96683 -3.88277 3.12502 2.55745 31.53064 1.43041 -1.83141 3.22322 2.36166 -2.33254 34.83906 |
2.09783 0.12073 4.51127 -3.20724 0.85930 |
33 |
28.46826 2.78937 -0.88293 1.02546 -0.80626 -1.90245 35.24233 2.16957 4.66379 -0.68137 -0.18789 1.73075 25.49616 3.15716 4.01921 -3.93404 3.16629 2.59122 31.94698 1.44930 -1.85559 3.26578 2.39285 -2.36334 35.29909
|
2.12553 0.12232 4.57084 -3.24959 0.87065 |
34 |
27.45419 2.69001 -0.85148 0.98893 -0.77754 -1.83469 33.98695 2.09228 4.49766 -0.65710 -0.18120 1.66910 24.58796 3.04470 3.87604 -3.79390 3.05350 2.49892 30.80899 1.39767 -1.78949 3.14945 2.30761 -2.27915 34.04169 |
2.04982 0.11797 4.40802 -3.13384 0.83963 |
35 |
27.82519 2.72636 -0.86299 1.00230 -0.78805 -1.85948 34.44623 2.12056 4.55844 -0.66598 -0.18365 1.69165 24.92023 3.08584 3.92842 -3.84517 3.09476 2.53268 31.22533 1.41656 -1.81367 3.19201 2.33880 -2.30995 34.50171 |
2.07752 0.11956 4.46759 -3.17618 0.85098 |
36 |
28.19620 2.76272 -0.87449 1.01566 -0.79855 -1.88427 34.90552 2.14883 4.61922 -0.67486 -0.18609 1.71421 25.25250 3.12699 3.98080 -3.89644 3.13603 2.56645 31.64166 1.43545 -1.83786 3.23457 2.36998 -2.34075 34.96174 |
2.10522 0.12115 4.52716 -3.21853 0.86232 |
37 |
28.56720 2.79907 -0.88600 1.02902 -0.80906 -1.90906 35.36480 2.17711 4.68000 -0.68374 -0.18854 1.73676 25.58477 3.16813 4.03318 -3.94771 3.17729 2.60022 32.05800 1.45434 -1.86204 3.27713 2.40116 -2.37155 35.42176 |
2.13292 0.12275 4.58672 -3.26088 0.87367 |
38 |
28.93820 2.83542 -0.89751 1.04239 -0.81957 -1.93386 35.82408 2.20538 4.74078 -0.69262 -0.19099 1.75932 25.91704 3.20927 4.08556 -3.99898 3.21855 2.63399 32.47434 1.47322 -1.88622 3.31969 2.43235 -2.40235 35.88178 |
2.16062 0.12434 4.64629 -3.30323 0.88502 |
39 |
28.93820 2.83542 -0.89751 1.04239 -0.81957 -1.93386 35.82408 2.20538 4.74078 -0.69262 -0.19099 1.75932 25.91704 3.20927 4.08556 -3.99898 3.21855 2.63399 32.47434 1.47322 -1.88622 3.31969 2.43235 -2.40235 35.88178 |
2.16062 0.12434 4.64629 -3.30323 0.88502 |
40 |
29.68021 2.90812 -0.92052 1.06912 -0.84058 -1.98344 36.74265 2.26193 4.86234 -0.71038 -0.19589 1.80443 26.58158 3.29156 4.19032 -4.10152 3.30108 2.70153 33.30701 1.51100 -1.93459 3.40481 2.49472 -2.46395 36.80183
|
2.21602 0.12753 4.76543 -3.38793 0.90771 |
41 |
30.05121 2.94447 -0.93203 1.08248 -0.85109 -2.00824 37.20193 2.29020 4.92312 -0.71926 -0.19834 1.82698 26.91385 3.33271 4.24269 -4.15278 3.34234 2.73530 33.72335 1.52989 -1.95877 3.44737 2.52590 -2.49475 37.26185 |
2.24372 0.12912 4.82500 -3.43028 0.91906 |
42 |
24.28830 2.37981 -0.75329 0.87489 -0.68788 -1.62312 30.06774 1.85101 3.97901 -0.58132 -0.16030 1.47662 21.75259 2.69360 3.42908 -3.35641 2.70138 2.21075 27.25624 1.23650 -1.58314 2.78627 2.04151 -2.01633 30.11616 |
1.81344 0.10436 3.89971 -2.77246 0.74281 |
43 |
28.24566 2.76756 -0.87603 1.01744 -0.79995 -1.88758 34.96676 2.15260 4.62733 -0.67604 -0.18642 1.71721 25.29680 3.13247 3.98778 -3.90328 3.14153 2.57096 31.69717 1.43797 -1.84108 3.24024 2.37414 -2.34486 35.02307 |
2.10891 0.12137 4.53510 -3.22418 0.86384 |
44 |
28.61667 2.80391 -0.88753 1.03081 -0.81046 -1.91237 35.42604 2.18088 4.68811 -0.68492 -0.18887 1.73977 25.62907 3.17362 4.04016 -3.95455 3.18279 2.60473 32.11351 1.45685 -1.86526 3.28280 2.40532 -2.37566 35.48310 |
2.13661 0.12296 4.59467 -3.26653 0.87518 |
45 |
28.98767 2.84027 -0.89904 1.04417 -0.82097 -1.93716 35.88532 2.20915 4.74889 -0.69380 -0.19132 1.76232 25.96134 3.21476 4.09254 -4.00581 3.22405 2.63849 32.52985 1.47574 -1.88945 3.32536 2.43651 -2.40646 35.94312 |
2.16431 0.12455 4.65423 -3.30888 0.88653 |
46 |
29.35867 2.87662 -0.91055 1.05753 -0.83148 -1.96196 36.34460 2.23742 4.80966 -0.70268 -0.19377 1.78488 26.29361 3.25591 4.14492 -4.05708 3.26532 2.67226 32.94619 1.49463 -1.91363 3.36792 2.46769 -2.43726 36.40314 |
2.19202 0.12615 4.71380 -3.35123 0.89788 |
47 |
29.72967 2.91297 -0.92205 1.07090 -0.84198 -1.98675 36.80389 2.26570 4.87044 -0.71156 -0.19621 1.80744 26.62588 3.29705 4.19730 -4.10835 3.30658 2.70603 33.36253 1.51352 -1.93781 3.41048 2.49887 -2.46805 36.86316 |
2.21972 0.12774 4.77337 -3.39358 0.90922 |
Составитель Трофимов Валерий Павлович
Редактор Тихомирова О.А.