Научная литература
booksshare.net -> Добавить материал -> Математика -> Боглаев Ю.П. -> "Вычислительная математика и программирование " -> 103

Вычислительная математика и программирование - Боглаев Ю.П.

Боглаев Ю.П. Вычислительная математика и программирование — Высшая школа, 1990. — 546 c.
ISBN 5-06-00623-9
Скачать (прямая ссылка): vychmatiprog1990.djvu
Предыдущая << 1 .. 97 98 99 100 101 102 < 103 > 104 105 106 107 108 109 .. 168 >> Следующая

319
системы уравнений (найти число обусловленности), так и вычислительную погрешность. Поэтому можно предложить следующие практические рекомендации:
1) для оценки числа обусловленности следует численно решить несколько систем уравнений с близкими правыми частями к заданному вектору Ъ\
2) для оценки вычислительной погрешности следует решить систему уравнений с двойной точностью.
8.2.5. Оценка числа арифметических операций метода Гаусса. Процесс исключения Гаусса запишем на фортране, используя обозначения 11к = Ь (I, К), аи = А (1,1), Ь{ = В (I), = X (I), п = И, массив Ь должен быть
описан как . вещественный. Имеем следующую программу
С ПРЯМЕЙ ход
ОО 1 К=1,М—1 ОО 1. 1 = К+1,К Ц1,К)‘= А(1,К)/А(К,К)
БО 10 1=К+1^
10 А(1,Л)=А(1Д) — Ц1,К)*А(КД)
1 В(1)=В(1)-Ц1,К)*В(К)
С ОБРАТНЫЙ ХОД
БО 3 К=1М,1,-1 Х(К)=0.
ОО 2 1 = К+1,И
2 Х(1)=Х(1)+А(КД)*Х(1)
3 Х(К) = (В(К)—Х(К))/А(К,К)
Здесь элементы матрицы а$ записываются в память на место исходной матрицы а1р элементы Ь\к)—на место вектора Ь{ (см. формулы (8.2.5), (8.2.7)).
Обратившись к тексту программы, замечаем, что при больших значениях порядка системы уравнений п основная вычислительная работа сосредоточена в трех вложенных циклах ОО 1. Число арифметических операций при п->оо есть 0(пъ), и основное время затрачивается на приведение матрицы к треугольному виду.
Для примера число арифметических операций решения системы уравнений с матрицей размером 100x 100 (т. е. л =100) имеет порядок 106. На ЭВМ с быстродействием 105 оп/с время решения такой системы будет порядка 10 с.
Если приведенный выше алгоритм дополнить выбором ведущего элемента исключения с частичным упорядочением, то между циклом по К и циклом по I появится еще один цикл
ИО 1 К= 1,14-1 ИО 11 М = К,Н
11 ССЖТШиЕ
ВО 1 1 = К+1,И
320
\
В этом цикле производится выбор ведущего элемента А (К, К), что потребует 0{п) арифметических операций (вычитания). Общее число арифметических операций при и-юо подсчитаем следующим образом: в циклах по 1,1 операций 0(п2) плюс в цикле по М: 0(п), откуда суммарное число операций
0(п) (О (п2) + 0(п)2) = 0(п3)
остается того же порядка, что и в алгоритме без упорядочения и основное время затрачивается на приведение матрицы к треугольному виду.
Наконец, легко понять, что цри полном упорядочении затраты на выбор ведущего элемента исключения сравниваются по порядку величины с приведением матрицы к треугольному виду.
8.2.6. Применение библиотечных программ. Вычисление определителя вещественной матрицы А с помощью программы А8А5 выполняется следующим образом. Для примера пусть
Тогда программа может иметь вид
REAL A(2,2),D,W(2)
INTEGER K,N,I DATA A/1.,2.,3.,4./,K,N,1/2,2,0/
С ОБРАЩЕНИЕ К ПРОГРАММЕ А8А5
CALL A8A5(A,K,N,D,W,I)
С ВЫВОД НА ТЕРМИНАЛ
WRITE (5,1) D,I 1 FORMAT (2X,'D = ',E13.6,'I = ',I2)
END
Решение системы линейных уравнений с симметричной положительно определенной матрицей
^=(l 4)’ Лх=ь’
и набором правых частей
с помощью программы А9А0 выполняется следующим образом:
REAL A(2,2),B(2,3),W(2),X(2,3),W(2,3)
INTEGER K,L,N,M,J,L,I
DATA A/3.,l.,l.,4./,B/l-,2.,3.,4.,5.,6./
DATA K,L,N,M,J,L 1,1/2,2,2,3,2,2,0/
С ОБРАЩЕНИЕ К ПРОГРАММЕ А9А0
CALL A9A0(A,K,B,L,N,M,X,J,W,W1 ,L 1,1)
С ВЫВОД НА ТЕРМИНАЛ
11 Ю. П. Боглаев
321
\VRITE (5,1) ХД 1 ЕОЯМАТ (2Х,'Х = ',/,6Е3.6,/Д = 'Д2) ЕЖ
ф 8.3. Итерационные методы решения систем линейных уравнений
8.3.1. Введение. Рассмотрим итерационные методы решения систем линейных уравнений. Эти методы, вообще говоря, не дают возможности найти точное решение за конечное число итераций даже при отсутствии вычислительной погрешности. С их помощью строится последовательность {х(к)} такая, что
1 1шис(к)=*,
' * ? 00
где л:—точное решение.
Область широкого применения итерационных методов—это системы уравнений, к которым приводят численные методы решения дифференциальных уравнений с частными производными. Матрицы таких систем имеют большое число нулевых элементов, и в отлйчйе от прямых методов итерационные не увеличивают число ненулевых элементов матрицы в процессе вычислений. Эффективность итерационных методов определяется скоростью сходимости последовательных приближений х{к) к решению. Пусть ищется решение невырожденной системы уравнений
Ах = Ъ. (8.3.1)
Первым шагом в итерационном методе является преобразование исходной системы к виду
Сх = Вх+с1, (8.3.2)
где матрицы С, В и вектор (I определяются по матрице А и вектору Ъ. Причем системы (8.3.1) и (8.3.2) являются эквивалентными, т. е. их решения совпадают, а построение обратной матрицы С-1 проще, чем А~К
Вторым шагом является расстановка индексов или номеров приближений в (8.3.2) и задание нулевого приближения. Например,
Сх(к+1) = Вх(к) + й, к=0, 1, 2, ... , (8.3.3)
где л:(0)—заданный вектор лг(0) = (х\0), ..., х^0)).
Третьим шагом итерационного метода является обоснование сходимости последовательных приближений {х(к)}, полученных из
(8.3.3), к точному решению л; системы (8.3.1) и оценка погрешности к-го приближения
|| х^к) — х || <8. (8.3.4)
Оценка (8.3.4) при заданном г позволяет остановить итерационный процесс (8.3.3).
Предыдущая << 1 .. 97 98 99 100 101 102 < 103 > 104 105 106 107 108 109 .. 168 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed