Пусть дана сист из n ур-ий с n неизвестными:

Пусть дана сист из n ур-ий с n неизвестными:

(1) {a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁; a₂₁x₁+a₂₂x₂+…+a_2nx_n=b₁;…;a_n1x₁+a_n2x₂+…+a_nnx_n=b_n

Коэффициенты a_ij при неизвестных и свободные члены b_i (i,j=1,2,…,n) принадлежат R.

Опр: Вектор х=(х₁…х_n) из Rⁿ наз-ся решением системы (1), если при подстановке его координат в систему каждое ур-е превращается в верное числовое равенство.

Будем считать, что определитель

|а₁₁ … а_1n;…;а_n1 … а_nn| не=0

Как известно, это обеспечивает существование и единственность реш-я на всем Rⁿ.

Существуют точные методы решения систем. Наиболее известными среди них явл-ся правило Крамера и метод Гаусса. Но при большом числе неизвестных схемы точного реш-я становятся сложными и требующими большого объема вычислений. В таких случаях обычно используются различные приближенные (итерационные) методы.

Метод итерации для систем линейных алгебраических ур-ий.

Чтобы воспользоваться принципом сжимающих отображений и построить итерационный процесс приближения к точному реш-ю, сист (1) сначала приводят к виду:

(2) {x₁=c₁₁x₁+…+c_1nx_n+d₁; x₂=c₂₁x₁+…+c_2nx_n+d₂;…; x_n=c_n1x₁+…+c_nnx_n+d_n

сист (2) – приведенная система.

Обозначим:

С=(с₁₁ … с_1n;…; c_n1 … c_nn)

x=(x₁,…,x_n)

d=(d₁,…,d_n)

Тогда сист (2) можно записать в матричной форме: x=Cx+d (2’)

Существует два способа преобразования сист (1) к виду (2):

Пример: Пусть дана система общего вида:

(*) {5x₁-x₂+x₃=4; 0,5x₁+2x₂-x₃=1; x₁-x₂+4x₃=2

Способ1: Поделить ур-я на соответствующие диагональные коэф-ты (они не равны 0) и решить каждое из ур-ний относительно полученных на диагонали неизвестных с коэффициентом 1. Получим приведенную систему:

(**) {x₁=0,2x₂-0,2x₃+0,8; x₂=-0,25x₁+0,5x₃+0,5; x₃=-0,25x₁+0,25x₂+0,5

Здесь:

С=(0 0,2 -0,2; -0,25 0 0,5; -0,25 0,25 0),

d=(0,8; 0,5; 0,5)

Способ2: Вычленить единицу из каждого диагонального коэффициента и выразить полученные таким образом х₁,х₂,х₃ из 1,2,3-го ур-ний соответственно. Получим приведенную систему:

(***) {x₁=-4x₁+x₂-x₃+4; x₂=-0,5x₁-x₂+x₃+1; x₃=-x₁+x₂-3x₃+2

Здесь:

С=(-4 1 -1; -0,5 -1 1; -1 1 -3),

d=(4; 1; 2)

Матричная форма записи показывает, что приведенная система (2) представляет собой ур-е вида х=F(x) с отображением

F: x → Cx+d (3) (отображение переводящее пространство n-мерных векторов Rⁿ в себя)

Каждому вектору х=(х₁…х_n) это отображение ставит в соответствие единственный вектор у=F(x)=Cx+d, координаты которого вычисляются с помощью выражений в правой части сист (2):

y_i = (j=1 до n)∑ c_ijx_j+d_i (i=1…n).

Решение сист (2) явл-ся неподвижной точкой отображения F.

Рекуррентная формула (x_n+1=F(x_n)) в данном случае запишется так:

x^(k+1)=Cx^(k)+d (4)

или в координатной форме:

(5) {x₁^(k+1)=c₁₁x₁^(k)+…+c_1nx_n^(k)+d₁; …; x_n^(k+1)=c_n1x₁^(k)+…+c_nnx_n^(k)+d_n

Таким образом, взяв какой-либо вектор x⁽⁰⁾=(x₁⁽⁰⁾;…;x_n⁽⁰⁾) и подставив его координаты в правую часть сист (2), получим новый вектор F(x⁽⁰⁾)=Cx⁽⁰⁾+d, который примем за x⁽¹⁾=(x₁⁽¹⁾;…;x_n⁽¹⁾).

При этом, согласно (5):

{x₁⁽¹⁾=c₁₁x₁⁽⁰⁾+…+c_1nx_n⁽⁰⁾+d₁; …; x_n⁽¹⁾=c_n1x₁⁽⁰⁾+…+c_nnx_n⁽⁰⁾+d_n

Затем вычислением F(x⁽¹⁾) находим вектор Cx⁽¹⁾+d =(def) x⁽²⁾

Действуя далее по аналогии, получаем итерационную последовательность для сист (2).

Достаточное условие сходимости итерационной последовательности

Обозначим через (с чертой)х = (х₁, …, х_n) точное решение системы (2).

Выясним условия, при которых (5) последовательность сходиться к (с чертой) х в Rⁿ относительно метрик.

Как известно сходимость последовательности векторов во всех 3-х рассматриваемых нами метрических пространствах равносильна покоординатной сходимости. Значит, если удастся построить последовательность приближений к (с чертой) х на основе одного из расстояний, то эта последовательность будет сходиться к (с чертой) х и относительно остальных 2-х расстояний.

Пусть далее Х = Rⁿ_@, т.е. предполагаем, что расстояние между векторами х (х₁…х_n) и у (у₁…у_n) вычисляется по формуле: ро (х, у) = max|x_i - y_i| i = 1… n.

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

Т: если матрица С коэффициентов при неизвестных в правой части системы удовлетворяет условию:

q = max∑ |cij| < 1 (i = 1…n; j = 1…n),

то эта система имеет единственное решение (с чертой) х, а построенная последовательность (х^к) сходится к (с чертой) х при любом начальном приближении х⁰ из Х.

Для оценки погрешности приближенного вектора (х^к) при = (с чертой) х (к = 1, 2,…) имеют место формулы

ро (х^(к), (с чертой) х) <= qⁿ/(1-q) * max |x_i⁽¹⁾ – x_i⁽⁰⁾|,

ро (х^(к), (с чертой) х) <= qⁿ/(1-q) * max |x_i^(к) – x_i^(к-1)|.

Дата добавления: 2015-11-04