Кафедра: Автоматика и информационные технологии
"ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ"
Екатеринбург 2006
РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ
Одной из самых распространенных и важных задач вычислительной математики является решение системы линейных алгебраических уравнений (СЛАУ):
a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a21 xn = b2
……………………………………. .
an1 x1 + an1 x2 +… + ann xn = bn,
или в векторно-матричном виде:
Ax = B, (1)
где
а11 а12 ......а1n
а21 а22 -… .. а2n
А = ................
аn1 аn2 … . ann
b1
b2
B =
bn
x1
x2
x =
xn
Итерационные методы решения СЛАУ используются для решения СЛАУ большой размерности с разреженными матрицами, а также для уточнения решения СЛАУ, полученного с помощью прямого метода. Формулировка и применение итерационных методов требует определенных знаний и определенного опыта. Выбор эффективного итерационного метода решения конкретной задачи существенно зависит от ее характерных свойств и от архитектуры вычислительной машины, на которой будет решаться задача. Поэтому никаких общих правил выбора наилучшего итерационного метода решения не существует. Метод простой итерации приведен здесь как иллюстрация действия механизма вычисления решения на основе итерационной процедуры.
Суть метода состоит в следующем. От системы уравнений вида Ах = в (2) переходят к системе уравнений
x=Dх + С (3)
Например, от системы уравнений
а11х1+а12х2+а13х3=в1
а21х1+ а22х2+а23х3=в2 (4)
а31х1+а32х2+а33х3=в3
можно перейти к виду (3), выразив из первого уравнения х1, из второго - х2, из третьего - х3:
х1= - а12/а11х2 - а13/а11х3+в1/а11
х2= - а21/а22х1 - а23/а22х3+в2/а22 (5)
х3= - а31/а33х1 - а32/а33х2+ в3/а33
Приведение исходной системы уравнений в виду (3) можно осуществить различными способами. Например, в СЛАУ (4) из первого уравнения можно выразить х2, из второго - х1, из третьего - х3 и, переставив уравнения для сохранения порядка следования переменных в векторе решения х, снова прийти к виду (3). Естественно, что матрица D и вектор с будут уже иными. Возможны и другие способы преобразования исходных уравнений.
После преобразования (2) к виду (3) назначается нулевое приближение решения х (0):
х1 (0)
х (0) = х2 (0)
х3 (0).
Если приблизительно известны значения хi вектора решения х, то они выбираются в качестве нулевого приближения, если нет, то в качестве вектора х (0) выбирается любой вектор, например х (0) =С.
Первый шаг итерационного процесса состоит в вычислении приближения х (1):
х (1) = Dx (0) +С.
Например, назначив х (0) и подставив его в систему уравнений (3), получим:
х1 (1) = - а12/а11х (0) - а13/а11х3 (0) +в1/а11
х2 (1) = - а21/а22х1 (0) - а23/а22х3 (0) +в2/а22
х3 (0) = - а31/а33х1 (0) - а32/а33х2 (0) +в3/а33.
Далее вычисляем:
х (2) = Dx (1) +C
х (к) =Dх (к-1) +С
и т.д.
Достаточное условие сходимости метода итерации заключается в следующем, если норма матрицы D (обозначается ║D║) меньше 1, то система уравнений (3) имеет единственное решение х* и итерации сходятся к этому решению со скоростью геометрической прогрессии Иными словами, если
║D║<1, (6)
то
ℓim ║х (к) - х*║= 0
к→∞
и выполняется тождество
х*=Dх*+С.
В качестве нормы матрицы D используются нормы ║D║1 или
║D║∞: n
║D║1 = max ∑ | dij |,
j i=1
n
║D║∞= max ∑ | dij |.
i j=1
Аналогично вводятся нормы вектора х:
n
║х║1 = ∑ |хi|
i=1
║х║∞= max |xi|.
i
Из условия сходимости (6) ясно, что не всякое преобразование исходной системы (2) к виду (3) позволит получить решение уравнения на основе итерационного процесса, а только такое, которое обеспечит выполнение условия ║D║<1. ............
