ORIENTAL UNIVERSITETIQidiruvПоискSearch
Oriental universiteti nashriyotiIlmiy jurnallar platformasiПлатформа научных журналовScholarly journals platform

Toʻliq matnПолный текстFull text

Один из аспектов практического применения итерационного метода Гаусса – Зейделя решения системы линейных алгебраических уравнений

Alinazar Hojimetov, Abdusamat Alimov

Matn PDF dan avtomatik ajratilgan: ekran oʻqiydigan dasturlar, telefon va qidiruv uchun. Rasmiy nusxa — PDF.Текст извлечён из PDF автоматически — для программ чтения с экрана, телефонов и поиска. Официальная версия — PDF.Text was extracted from the PDF automatically for screen readers, phones and search. The PDF remains the version of record.

PDF ni oʻqishЧитать PDFRead the PDF → Nashr kartasiКарточка изданияRecord

ОДИН ИЗ АСПЕКТОВ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ
ИТЕРАЦИОННОГО МЕТОДА ГАУССА – ЗЕЙДЕЛЯ РЕШЕНИЯ

СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Alinazar HOJIMETOV,
Банковская академия финансов;

Abdusamat ALIMOV,
Университет Ориентал, PhD

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

Ключевые слова: матрица, метод Зейделя, система линейных
алгебраических уравнений.

Annotatsiya. Mexanika fani ko‘plab masalalari miqdoriy yechilganida,
masala, chiziqli algebraik tenglamalar sistemasini yechishga kelib qoladi. Bunda
sistema asosiy matritsasi “salbiy” matritsa bo‘lib, uning determinati deyarli nolga
teng bo‘ladi, hamda ko‘plab elementlari nol bo‘ladi. Bunday sistemalarni yechishda,
avval ular har xil usullar bilan “yaxshi”lanadi (regulyarizatsiya qilinadi), yoki
sistema taqriban Gauss-Zeydel iteratsion usuli yordamida yechiladi. Bu usulning
asosiy talablaridan biri, asosiy matritsa bosh diagonali elementlari noldan farqli
bo‘lishidir. Bu maqolada bosh diagonal elementlarini noldan farqli qilish bilan birga,
usulning yaqinlashishini taʼminlovchi metod keltirilgan.

Kalit so‘zlar: matritsa, Zeydel usuli, chiziqli algebraik tenglamalar sistemasi.

Annotation. The numerical solution of a large number of problems in
mechanics is reduced to solving systems of linear algebraic equations with sparse
and ill-conditioned matrices. In such cases, various methods of system regularization
are used. Also, one can resort to the iterative Gauss-Seidel method, one of the main
requirements of which is that the elements of the main diagonal of the main matrix
are not equal to zero. If this condition is not met, the method does not work. This
article proposes one way to solve this issue, which also leads to good convergence.

Key words: matrix, Seidel method, system of linear algebraic equations.

Большое количество задач техники и механики, к решению которых
применяется метод конечных элементов или метод граничных элементов
сводятся к решению систем линейных алгебраических уравнений (СЛАУ) с
разреженными матрицами, что приводит к определенным трудностям. При
этом приходится иметь дело с плохо обусловленными матрицами. Для
отыскания решений этих СЛАУ используются различные методы, например,
метод регуляризации Тихонова. Применение этого метода приведен и
представляет собой подбор коэффициента регуляризации, при котором
определитель основной матрицы получается отличным от нуля, но может быть
потерян основной смысл задачи.111

В этом смысле, более подходящим является метод Гаусса – Зейделя (в
литературе больше известно как метод Зейделя). Метод является
классическим итерационным методом и хорошо подходит для решения СЛАУ
с разреженными матрицами.

Рассмотрим систему:

𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛𝑥𝑛 = 𝑏1

{ ……………………………………… (1)

𝑎𝑛1𝑥1 + 𝑎𝑛2𝑥2 + ⋯ + 𝑎𝑛𝑛𝑥𝑛 = 𝑏𝑛

Суть метода Зейделя, являющейся модификацией метода Якоби, состоит

в том, что новые значения неизвестных используются здесь сразу же, по мере

получения. Рассмотрим алгоритм метода на примере решения СЛАУ третьего

порядка:

𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 = 𝑏1

{𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 = 𝑏2 (2)

𝑎31𝑥1 + 𝑎32𝑥2 + 𝑎33𝑥3 = 𝑏3

И пусть диагональные элементы основной матрицы отличны от нуля, а
также известно некоторое начальное (приближенное) решение 𝑥1(0), 𝑥2(0), 𝑥3(0) .

Из (2) для первого и последующих приближений имеем (i – номер
приближения, i=0, 1, 2, …):

Из (3) видно, что новые значения неизвестных используются здесь сразу
же по мере получения. Процесс продолжается до выполнения условия
бесконечной малости (или малости в с требуемой точностью >0) суммы
квадратов двух последовательных приближений:

111 Калиткин Н.Н. Численный анализ. – Москва: Академия. – C. 348.

𝑥1(𝑖+1) = − 𝑎12 𝑎 𝑥 11 2(𝑖) − 𝑎13 𝑎 𝑥 11 3(𝑖) + 𝑏1 𝑎11 (3)
𝑥2(𝑖+1) = − 𝑎21 𝑎 𝑥 22 1(𝑖+1) − 𝑎23 𝑎 𝑥 22 3(𝑖) + 𝑏2 𝑎22
{𝑥3(𝑖+1) = − 𝑎31 𝑎 𝑥 33 1(𝑖+1) − 𝑎32 𝑎 𝑥 33 2(𝑖+1) + 𝑏3 𝑎33

Рассмотрим алгоритм метода в случае СЛАУ n-го порядка (1). Для
простоты предположим, что все элементы главной диагонали основной
матрицы отличны от нуля.

Если это не так, что является основным вопросом, решению которого и
посвящена настоящая работа, то с помощью элементарных преобразований
можно прийти к этому. Этот вопрос мы рассмотрим в дальнейшем. Пусть нам
известно начальное приближенное решение 𝑥1(0), 𝑥2(0), … , 𝑥𝑛(0) .

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

𝑥1(𝑖+1) = − 𝑎12 𝑎 𝑥 11 2(𝑖) − 𝑎13 𝑎 𝑥 11 3(𝑖) − ⋯ − 𝑎1𝑛 𝑎 𝑥 11 𝑛(𝑖) + 𝑏1 𝑎11
𝑥2(𝑖+1) = − 𝑎21 𝑎 𝑥 22 1(𝑖+1) − 𝑎23 𝑎 𝑥 22 3(𝑖) − ⋯ 𝑎2𝑛 𝑎 𝑥 22 𝑛(𝑖) + 𝑏2 𝑎22 (4)

………………………
{𝑥𝑛(𝑖+1) = − 𝑎𝑛1 𝑎 𝑥 𝑛𝑛 1(𝑖+1) − 𝑎𝑛2 𝑎 𝑥 𝑛𝑛 2(𝑖+1) − ⋯ − 𝑎𝑛(𝑛−1) 𝑎 𝑥 𝑛𝑛 𝑛−1 (𝑖+1) + 𝑏𝑛 𝑎𝑛𝑛

Как было сказано выше, итерационный процесс продолжается до
выполнения условия бесконечной малости (или малости в с требуемой
точностью >0) дисперсии решений в двух последовательных приближениях:

1 𝑛 (𝑖+1) 𝑖 2

𝑛√ ∑ (𝑥𝑘 − 𝑥𝑘) < 𝜀 (5)

𝑘=1

При выполнении условия (5) процесс останавливается и решением СЛАУ
(1) с точностью >0 будут значения 𝑥1(𝑖+1), 𝑥2(𝑖+1), … , 𝑥𝑛(𝑖+1).

Как видно, приведенный выше алгоритм решения справедлив, если для i

– го уравнения aii0. Если это требование нарушено, то в рассмотренном выше
виде метод Зейделя не работает, т.к. коэффициенты итерационных уравнений

делятся на aii. В этом случае необходимо поменять местами уравнения таким
образом, чтобы все коэффициенты aii были отличны от нуля.

Для решения этого вопроса поступим следующим образом: пусть aii=0,
т.е. элемент главной диагонали равен нулю. При этом проанализируем все
коэффициенты системы, перед переменной xi, т.е. все элементы i-го столбца
основной матрицы системы, и определим наибольший из них по модулю,
пусть это будет элемент aki , т.е. элемент находящийся на пересечении k-й
строки и j-го столбца. Поменяем местами k-е и i-е уравнения и вопрос будет
решен. Как известно, замена местами двух уравнений в СЛАУ никоим
образом не влияет на результат.

Также, важным является условие сходимости метода Зейделя.
Приводится теорема и доказательство достаточных условий сходимости
метода Зейделя.112

Теорема 1. Для существования единственного решения системы (1) и
сходимости метода Зейделя достаточно выполнения хотя бы одного из двух
условий:

𝑎) ∑|𝑎𝑖𝑗| < |𝑎𝑖𝑖| , 𝑖 = 1,2, … , 𝑛;

𝑗≠𝑖

б) матрица А – симметричная положительно определенная (все ее
собственные значения положительны).

Ниже приводится программа-макрос, составленная в среде Visual Basic, в
которой реализован вопрос практического применения метода Зейделя в
случае равенства нулю одного или нескольких элементов главной диагонали
основной матрицы системы линейных алгебраических уравнений.
sub zeydel 2 ()
Dim a (1 To 100, 1 To 100), c(1 To 100, 1 To 100)
Dim t (1 To 100, 1 To 100), r(1 To 100)
Dim x (1 To 100, 1 To 1000), b(1 To 100), d(1 To 100), maxk (1 To 100)
Sheets ("dannie"). Select
n = Cells (1, 1)
eps = Cells (1, 2)
For i = 1 To n
For j = 1 To n
a (i, j) = Cells (i + 1, j)
Next j

112 А.Абидов, И.Атабеков, Ф.Долгополов, А.Ходжиметов. Численное геодинамическое моделирование
палеорифтовой системы востока Туранской платформы. // Доклады АН РУз. – Ташкент, 1996. - № 12. – С.
44-46.

b (i) = Cells (i + 1, n + 1) - 105 -
Next i
For j = 1 To n
A_max = 0
For i = 1 To n
If Abs (a(i, j)) > A_max Then
A_max = Abs (a(i, j))
maxk (j) = i
End If
Next i
Next j
For i = 1 To n
If Abs (a(i, i)) < eps Then
For j = 1 To n
a (i, j) = a(i, j) + a (maxk(i), j)
Next j
b (i) = b(i) + b (maxk(i))
End If
Next I
For i = 1 To n
For j = 1 To n
Cells (i + 9, j) = a (i, j)
Next j
Cells (i + 9, n + 1) = b (i)
Next i
For i = 1 To n
For j = 1 To n
c (i, j) = - a (i, j) / a (i, i)
Next j
d (i) = b (i) / a (i, i)
x (i, 1) = 0
Next i
ii1 = 20
k = 1
met2:
For i = 1 To n
Sum = 0
For j = 1 To n

ISSN 3030-3273

If j <= i Then
Sum = Sum + x (j, k + 1) * c (i, j)
Else
Sum = Sum + x (j, k) * c (i, j)
End If
Next j
x (i, k + 1) = Sum + d (i)
Cells (ii1, 1) = i
Cells (ii1, 2) = k + 1
Cells (ii1, 3) = x (i, k + 1)
ii1 = ii1 + 1
Next i
Sumus = 0
For i = 1 To n
Sumus = Sumus + ((x(i, k + 1) - x(i, k)) ^ 2) / n
Next i
Sumus = (Sumus) ^ 0.5
If Sumus > eps Then
Cells(n + 29, 2) = Sumus
k = k + 1
GoTo met 2
End If
End Sub

Таким образом, предложенный в статье простой способ позволяет
выполнить требование метода Гаусса-Зейделя при численном решении
итерационным способом, а также улучшает скорость сходимости.
Приведенный несложный алгоритм может быть адаптирован при
использовании также и других программных систем.

Список использованной литературы:

1. А.Абидов, И.Атабеков, Ф.Долгополов, А.Ходжиметов. Численное
геодинамическое моделирование палеорифтовой системы востока Туранской платформы.
// Доклады АН РУз. – Ташкент, 1996. - № 12. – С. 44-46.

2. А.Абидов, И.Атабеков, Ф.Долгополов, А.Ходжиметов. Численное математическое
моделирование наклонных разрывных структур в земной коре Сурхандарьинского
нефтегазоносного региона. // Доклады АН РУз. – Ташкент, 2001. – № 3. – С. 27-29.

3. Атабеков И.У. Геодинамическая модель орогенеза Памиро-Гиндукуша: Дис. на
докт. физ.-мат. наук. – Ташкент, 1994. – 170 c.

4. С.Крауч, А.Старфильд. Метод граничных элементов в механике твердого тела. –
Москва: Мир, 1987. – 326 c.

5. А.Abidov, I.Atabekov, F.Dolgopolov, A.Hodjimetov. Strain State of the Crust of some
Regions of the Central Asia. // Contemporary Research in Theoretical and Applied Mechanics.
Proceedings. – Blacksburg, 2002. – Р. 582-583.

6. Волков Е.А. Численные методы: Учеб. пособие для ВУЗов. – Москва: Наука, 1987.
– 248 c.

7. О.Убайдиллаев, А.Ходжиметов. Алгоритм решения двумерных задач теории
упругости по методу граничных интегральных уравнений. // Вестник ТашГТУ. – Ташкент,
2003. – № 1. – С. 6-10.

8. Калиткин Н.Н. Численный анализ. – Москва: Aкадемия. – 348 c.
9. Бахвалов Н.С. Численные методы. – Москва: Бином, 2016. – 352 c.