Метод гаусса зейделя реферат

Обновлено: 05.07.2024

Метод Зейделя представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной xi учитываются уже вычисленные ранее (k+1) – е приближения неизвестных x1, х2, .

В этом методе, как и в методе простой итерации, необходимо привести систему к виду (3), чтобы диагональные коэффициенты были максимальными по модулю, и проверить условия сходимости. Если условия сходимости не выполняются, то нужно произвести элементарные преобразования (см. п. 4). Пусть дана система из трех линейных уравнений. Приведем ее к виду (3). Выберем произвольно начальные приближения корней: х1(0), х2(0), х3(0), стараясь, чтобы они в какой-то мере соответствовали искомым неизвестным. За нулевое приближение можно принять столбец свободных членов, т. е. х(0) = b

(т. е. x1(0)=b1, x2(0)=b2, x3(0)=b3). Найдем Первое приближение х(1) по формулам:

Следует обратить внимание на особенность метода Зейделя, которая состоит в том, что полученное в первом уравнении значение х1(l) сразу же используется во втором уравнении, а значения х1(1), х2(1) – в третьем уравнении и т. д. То есть все найденные значения х1(1) подставляются в уравнения для нахождения хi+1(1) [6, 8].

Рабочие формулы для метода Зейделя для системы трех уравнений имеют следующий вид:

Запишем в общем виде для системы n-уравнений рабочие формулы:

Заметим, что теорема сходимости для метода простой итерации справедлива и для метода Зейделя.

Зададим определенную точность решения e, по достижении которой итерационный процесс завершается, т. е. решение продолжается до тех пор, пока не будет выполнено условие для всех уравнений: где i=1,2,3,…,n.

Пример №2. Методом Зейделя решить систему с точностью e = 10-3:

1. Приведем систему к виду:

2. В качестве начального вектора х(0) возьмем элементы столбца свободных членов, округлив их значения до двух знаков после запятой:

3. Проведем итерации методом Зейделя. При k = 1

При вычислении х2(1) используем уже полученное значение х1(1) =

При вычислении х3(1) используем значения х1(1) и х2(1):

Наконец, используя значения х1(1), х2(1), х3(1), получаем:

Аналогичным образом ведем вычисления при k=2 и k=3. При k= 2:

Найдем модули разностей значений при k = 2:

Они меньше заданного числа e, поэтому в качестве решения возьмем: x1 = 0,80006, x2 = 1,00002, x3 = 1,19999, x4 = 1,40000.

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

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

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

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 100 тыс. уравнений в формате двойной точности заняла бы около 75 Гбайт).

1. Теоретическая часть

1.1. Метод Гаусса

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных ) известен в различных вариантах уже более 2000 лет.

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

1.1.1. Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления .

Прямой ход состоит из n - 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x 1 из уравнений с номерами i = 2, 3, …, n . Предположим, что коэффициент a 11 ¹ 0. Будем называть его главным элементом 1-го шага .

называемые множителями 1-го шага . Вычтем последовательно из второго, третьего, …, n- го уравнений системы первое уравнение, умноженное соответственно на q2 1 , q 31 , …, qn 1 . Это позволит обратить в нуль коэффициенты при x 1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n xn = b 1 ,

a 22 (1) x 2 + a 23 (1) x 3 + … + a 2n (1) xn = b 2 (1) ,

a 32 (1) x 2 + a 33 (1) x 3 + … + a 3n (1) xn = b 3 (1) ,

в которой aij (1) и bij (1) вычисляются по формулам

2-й шаг. Целью этого шага является ислючение неизвестного x 2 из уравнений с номерами i = 3, 4, …, n . Пусть a 22 (1) ≠ 0, где a 22 (1) ­– коэффициент, называемый главным (или ведущим ) элементом 2-го шага . Вычислим множители 2-го шага

и вычтем последовательно из третьего, четвертого, …, n- го уравнения системы второе уравнение, умноженное соответственно на q 32 , q 42 , …, qm 2 . В результате получим систему

a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n xn = b 1 ,

a 22 (1) x 2 + a 23 (1) x 3 + … + a 2n (1) = b 2 (1) ,

a 33 (2) x 3 + … + a 3n (2) xn = b 3 (2) ,

Здесь коэффициенты aij (2) и bij (2) вычисляются по формулам

Аналогично проводятся остальные шаги. Опишем очередной k- й шаг.

k- й шаг. В предположении, что главный (ведущий ) элемент k- го шага akk (k –1) отличен от нуля, вычислим множители k-го шага

qik = aik (k –1) / akk (k –1) (i = k + 1, …, n )

и вычтем последовательно из (k + 1)-го, …, n -го уравнений полученной на предыдущем шаге системы k -e уравнение, умноженное соответственно на qk +1,k , qk +2,k , …, qnk .

После (n - 1)-го шага исключения получим систему уравнений

a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1n xn = b 1 ,

a 22 (1) x 2 + a 23 (1) x 3 + … + a 2n (1) xn = b 2 (1) ,

a 33 (2) x 3 + … + a 3n (2) xn = b 3 (2) ,

ann (n –1) xn = bn (n –1) .

матрица A (n -1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn –1 . Осуществляя обратную подстановку, далее последовательно находим xn –1 , xn –2 , …, x 1 . Вычисления неизвестных здесь проводятся по формулам

xn = bn (n –1) / ann (n –1) ,

xk = (bn (k –1) – ak ,k +1 (k –1) xk +1 – … – akn (k –1) xn ) / akk (k –1) , (k = n – 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk (k –1) . Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

1.1.2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k -м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

aij (k ) = aij (k –1) − qik akj , bi (k ) = bi (k –1) − qik bk (k –1) , i = k + 1, …, n .

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

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |qik | ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n . Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k -м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n . Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k -м уравнением системы для того, чтобы главный элемент занял место коэффициента akk (k -1) . После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.

1.1.3. Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.

На 1-м шаге мтода среди элементов aij определяют максимальный по модулю элемент ai 1j 1 . Первое уравнение системы и уравнение с номером i 1 меняют местами. Далее стандартным образом производят исключение неизвестного xi 1 из всех уравнений, кроме первого.

На k -м шаге метода среди коэффициентов aij (k –1) при неизвестных в уравнениях системы с номерами i = k , …, n выбирают максимальный по модулю коэффициент aikjk (k -1) . Затем k -е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n .

На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn , xjn– 1 , …, xj 1 .

1.2. Метод Зейделя

1.2.1. Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений

Ax = b

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

x = Bx + c .

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

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

x 1 = b 11 x 1 + b 12 x 2 + b 13 x 3 + … + b 1n xn + c 1

x 2 = b 21 x 1 + b 22 x 2 + b 23 x 3 + … + b 2n xn + c 2

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

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

x 1 = a 11 –1 (b 1a 12 x 2a 13 x 3 – … – a 1n xn ),

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

x 2 = a 21 –1 (b 2a 22 x 2a 23 x 3 – … – a 2n xn ),

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

x 1 = b 12 x 2 + b 13 x 3 + … + b 1,n –1 xn –1 + b 1n xn + c 1 ,

x 2 = b 21 x 1 + b 23 x 3 + … + b 2,n –1 xn –1 + b 2n xn + c 2 ,

x 3 = b 31 x 1 + b 32 x 2 + … + b 3,n –1 xn –1 + b 3n xn + c 3 ,

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

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

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

1.2.1. Описание метода. Введем нижнюю и верхнюю треугольные матрицы

0 0 0 … 0 0 b 12 b 13b 1n

b 21 0 0 … 0 0 0 b 23b 2n

B 1 = b 31 b 32 0 … 0 , B­­ 2 = 0 0 0 … b 3n

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

x = B 1 x + B 2 x + c .

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

x (1) = B 1 x (0) + B 2 x (1)

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

x (2) = B 1 x (1) + B 2 x (2)

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

x (k +1) = B 1 (k +1) + B 2 (k ) + c

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

x1 (k +1) = b 12 x 2 (k ) + b 13 x 2 (k ) + … + b 1n xn (k ) + c 1 ,

x2 (k +1) = b 21 x 1 (k +1) + b 23 x 3 (k ) + … + b 2n xn (k ) + c 2 ,

x3 (k +1) = b 31 x 1 (k +1) + b 32 x 2 (k +1) + … + b 3n xn (k ) + c 3 ,

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

xi (k +1) = x i (k ) – aii –1 (∑j =1 i –1 aij xj (k +1) + ∑j =1 n aij xi (k ) – bi ).

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

j =1, j≠i n | ij | m then begin

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

Содержание

1. Теоретическая часть 1

1.1. Метод Гаусса 1

1.2. Метод Зейделя 4

1.3. Сравнение прямых и итерационных методов 6

2. Практическая часть 7

2.1 Программа решения системы линейных уравнений по методу Гаусса 7

2.2 Программа решения системы линейных уравнений по методу Зейделя 10

Введение

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

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

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

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 100 тыс. уравнений в формате двойной точности заняла бы около 75 Гбайт).

1. Теоретическая часть

1.1. Метод Гаусса

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

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

1.1.1. Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

Прямой ход состоит из n  1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x1 из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a11  0. Будем называть его главным элементом 1-го шага.

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q21, q31, …, qn1. Это позволит обратить в нуль коэффициенты при x1 во всех уравнениях, кроме первого. В результате получим эквивалентную систему

в которой aij (1) и bij (1) вычисляются по формулам

2-й шаг. Целью этого шага является ислючение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22 (1) ? 0, где a22 (1) ­– коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2. В результате получим систему

Здесь коэффициенты aij (2) и bij (2) вычисляются по формулам

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага akk ( k –1) отличен от нуля, вычислим множители k-го шага

qik = aik ( k –1) / akk ( k –1) (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk+1,k, qk+2,k, …, qnk.

После (n - 1)-го шага исключения получим систему уравнений

ann ( n –1) xn = bn ( n –1) .

матрица A ( n -1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn–1. Осуществляя обратную подстановку, далее последовательно находим xn–1, xn–2, …, x1. Вычисления неизвестных здесь проводятся по формулам

xn = bn ( n –1) / ann ( n –1) ,

xk = (bn ( k –1) – ak,k+1 ( k –1) xk+1 – … – akn ( k –1) xn) / akk ( k –1) , (k = n – 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk ( k –1) . Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

1.1.2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

aij ( k ) = aij ( k –1) ? qikakj , bi ( k ) = bi ( k –1) ? qikbk ( k –1) , i = k + 1, …, n.

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

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |qik| ? 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk ( k -1) . После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.

1.1.3. Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.

На 1-м шаге мтода среди элементов aij определяют максимальный по модулю элемент ai1j1. Первое уравнение системы и уравнение с номером i1 меняют местами. Далее стандартным образом производят исключение неизвестного xi1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов aij ( k –1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент aikjk ( k -1) . Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn, xjn–1, …, xj1.

1.2. Метод Зейделя

1.2.1. Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений

Ax = b

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

x = Bx + c.

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

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

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

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

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

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

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

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

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

1.2.1. Описание метода. Введем нижнюю и верхнюю треугольные матрицы

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

x = B1x + B2 x + c .

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

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

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

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

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

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

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

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 ,

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

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

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

?j=1, j?i n | ij | m then begin

  • Для учеников 1-11 классов и дошкольников
  • Бесплатные сертификаты учителям и участникам

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

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

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

Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (матрица системы из 100 тыс. уравнений в формате двойной точности заняла бы около 75 Гбайт).

1 .Глава. Модификация метода простых итераций

1.1.Метод Зейделя

Модификацией метода простых итераций Якоби можно считать метод Зейделя.

В методе Якоби на (k+1)-ой итерации значения x , i = 1, 2, …, n. вычисляются подстановкой в правую часть (3.27) вычисленных на предыдущей итерации значений x . В методе Зейделя при вычислении x используются значения x , x , x , уже найденные на (k+1)-ой итерации, а не x , x , …, x , как в методе Якоби, т.е. (k + 1)-е приближение строится следующим образом:

x = b12 x + b13 x + … + b1,n-1 x + b1n x + c1

x = b21 x + b23 x + … + b2,n-1 x + b2n x + c2

x = b31 x + b32 x + … + b3,n-1 x + b3n x + c3 (3.36)

x = bn1 x + bn2 x x + bn3 x x + … + bn,n-1 x + c.n

Формулы (3.36) являются расчетными формулами метода Зейделя.

Введем нижнюю и верхнюю треугольные матрицы:

0 0 0 … 0 0 b12 b13 … b1n

b21 0 0 … 0 0 0 b23 … b2n

B 1 = b31 b32 0 … 0 и B 2 = 0 0 0 … b3n .

bn1 bn2 bn3 …0 0 0 0 … 0

Матричная запись расчетных формул (3.36) имеет вид:

xk+1= B1xk+1+ B2xk+ c. (3.37)

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

Читайте также: