Метод Гаусса — Зейделя. Гаусса метод реферат

Реферат: Матрицы Метод Гаусса

КОСТРОМСКОЙ ФИЛИАЛ ВОЕННОГО УНИВЕРСИТЕТА РХБ ЗАЩИТЫ

Кафедра «Автоматизации управления войсками»

Только для преподавателей

"Утверждаю"

Начальник кафедры № 9

полковник ЯКОВЛЕВ А.Б.

«____»______________ 2004 г.

доцент СМИРНОВА А.И.

"МАТРИЦЫ. МЕТОД ГАУССА"

ЛЕКЦИЯ № 2 / 3

Обсуждено на заседании кафедры № 9

«____»___________ 2003г.

Протокол № ___________

Кострома, 2003

Cодержание

Введение

1. Действия над матрицами.

2. Решение систем линейных уравнений методом Гаусса.

Заключение

Литература

1. В.Е. Шнейдер и др., Краткий курс высшей математики,том I, гл.2,§6, 7.

2. В.С. Щипачев, Высшая математика, гл. 10, § 1, 7.

ВВЕДЕНИЕ

На лекции рассматривается понятие матрицы, действия над над матрицами, а также метод Гаусса для решения систем линейных уравнений. Для частного случая, так называемых квадратных матриц, можно вычислять определители, понятие о которых рассмотрено на предыдущей лекции. Метод Гаусса является более общим, чем рассмотренный ранее метод Крамера решения линейных систем. Разбираемые на лекции вопросы используются в различных разделах математики и в прикладных вопросах.

1-ый учебный вопросДЕЙСТВИЯ НАД МАТРИЦАМИ

ОПРЕДЕЛЕНИЕ 1.Прямоугольная таблица изm,nчисел, содержащаяm– строк иn– столбцов, вида:

называетсяматрицей размераm´n

Числа, из которых составлена матрица, называютсяэлементами матрицы.

Положение элементааijв матрице характеризуются двойным индексом:

первыйi– номер строки;

второйj– номер столбца, на пересечении которых стоит элемент.

Сокращенно матрицы обозначают заглавными буквами:А, В, С…

Коротко можно записывать так:

ОПРЕДЕЛЕНИЕ 2.Матрица, у которой число строк равно числу столбцов, т.е.m=n, называетсяквадратной.

Число строк (столбцов) квадратной матрицы называется порядком матрицы.

ПРИМЕР.

ЗАМЕЧАНИЕ 1. Мы будем рассматривать матрицы, элементами которых являются числа. В математике и ее приложениях встречаются матрицы, элементами которых являются другие объекты, например, функции, векторы.

ЗАМЕЧАНИЕ 2. Матрица – специальное математическое понятие. С помощью матриц удобно записывать различные преобразования, линейные системы и т.д., поэтому матрицы часто встречаются в математической и технической литературе.

ОПРЕДЕЛЕНИЕ 3.Матрица размера1 ´n, состоящая из одной строки, называетсяматрицей – строкой.

Матрица размера т´ 1, состоящая из одного столбца, называетсяматрицей – столбцом.

ОПРЕДЕЛЕНИЕ 4.Нулевой матрицейназывают матрицу, все элементы которой равны нулю.

Рассмотрим квадратную матрицу порядкаn:

побочная диагональ

главная диагональ

Диагональ квадратной матрицы, идущая от верхнего левого элемента таблицы к правому нижнему, называетсяглавной диагональю матрицы(на главной диагонали стоят элементы видааii).

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

Рассмотрим некоторые частные виды квадратных матриц.

1) Квадратная матрица называетсядиагональной, если все элементы, не стоящие на главной диагонали, равны нулю.

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

3) Квадратная матрица называетсятреугольной,если все элементы, расположенные по одну сторону от главной диагонали, равны нулю:

верхняя нижняя

треугольная матрица треугольная матрица

Для квадратной матрицы вводится понятие:определитель матрицы. Это определитель, составленный из элементов матрицы. Обозначается:

Ясно, что определитель единичной матрицы равен 1: ½Е½ = 1

ЗАМЕЧАНИЕ. Неквадратная матрица определителя не имеет.

Если определитель квадратичной матрицы отличен от нуля, то матрица называетсяневырожденной, если определитель равен нулю, то матрица называетсявырожденной.

ОПРЕДЕЛЕНИЕ 5.Матрица, полученная из данной заменой ее строк столбцами с теми же номерами, называетсятранспонированной к данной.

Матрицу, транспонированную кА, обозначаютАТ.

ПРИМЕР.

23 32

ОПРЕДЕЛЕНИЕ.Две матрицы одного и того же размера называютсяравными,если равны все их соответственные элементы.

Рассмотрим действия над матрицами.

СЛОЖЕНИЕ МАТРИЦ.

Операция сложения вводится только для матриц одинакового размера.

ОПРЕДЕЛЕНИЕ 7.Суммой двух матриц А = (аij) и В = (bij) одинакового размераназывается матрица С = (сij)того же размера, элементы которой равны суммам соответствующих элементов слагаемых матриц, т.е. сi j =ai j+ bi j

Обозначается сумма матрицА + В.

ПРИМЕР.

УМНОЖЕНИЕ МАТРИЦ НА ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО

ОПРЕДЕЛЕНИЕ 8.Чтобы умножить матрицу на числоk, надо умножить на это число каждый элемент матрицы:

еслиА=(аij), тоk·A=(k·aij)

ПРИМЕР.

СВОЙСТВА СЛОЖЕНИЯ МАТРИЦ И УМНОЖЕНИЯ НА ЧИСЛО

1. Переместительное свойство:А + В = В + А

2. Сочетательное свойство:( А + В ) + С = А + ( В + С )

3. Распределительное свойство:k·(A+B) =kA+kB, гдеk–число

УМНОЖЕНИЕ МАТРИЦ

МатрицуАназовем с о г л а с о в а н н о й с матрицейВ, если число столбцов матрицыАравно числу строк матрицыВ, т.е. для согласованных матриц матрицаАимеет размерm´n, матрицаВимеет размерn´k.Квадратные матрицы согласованы, если они одного порядка.

ОПРЕДЕЛЕНИЕ 9.Произведением матрицы А размераm´nна матрицу В размераn´kназывается матрица С размераm´k, элемент которой аij, расположенный вi–ой строке иj– ом столбце, равен сумме произведений элементовi– ой строки матрицы А на соответствующие элементыj– столбца матрицы В, т.е.

cij=ai1b1j+ai2b2j+……+ainbnj

Обозначим:С = А·В.

Еслито

ПроизведениеВ´Ане имеет смысла, т.к. матрицыне согласованы.

ЗАМЕЧАНИЕ 1. ЕслиА´Вимеет смысл, тоВ´Аможет не иметь смысла.

ЗАМЕЧАНИЕ 2. Если имеет смыслА´ВиВ´А, то, вообще говоря

А´В¹В´А, т.е. умножение матриц не обладает переместительным законом.

ЗАМЕЧАНИЕ 3. ЕслиА– квадратная матрица иЕ– единичная матрица того же порядка, тоА´Е=Е´А = А.

Отсюда следует, что единичная матрица при умножении играет роль единицы.

ПРИМЕРЫ. Найти , если можно,А´ВиВ´А.

Решение: Квадратные матрицы одного и того же второго порядка согласованы в томи другом порядке, поэтомуА´ВиВ´Асуществуют.

Решение: МатрицыАиВсогласованы

МатрицыВиАне согласованы, поэтомуВ´Ане имеет смысла.

Отметим, что в результате перемножения двух матриц получается матрица, содержащая столько строк, сколько их имеетматрица–множимоеи столько столбцов, сколько их имеетматрица-множитель.

СВОЙСТВА УМНОЖЕНИЯ МАТРИЦ

1. Сочетательное свойство:А´( В´С ) = (А´В )´С

2. Распределительное свойство:(А+В)´С = А´С + В´С

Можно показать, что , еслиАиВ– две квадратные матрицы одного порядка с определителями ½А½ и ½В½, то определитель матрицыС=А´Вравен произведению определителей перемножаемых матриц, т.е.

½С½ = ½А½ ½В½

Отметим следующий любопытный факт. Как известно, произведение двух отличных от нуля чисел не равно нулю. Для матриц подобное обстоятельство может и не иметь места, т.е. произведение двух ненулевых матриц может оказаться равнымнуль - матрице.

Действие "деление" для матриц не вводится. Для квадратных невырожденных матриц вводится обратная матрица. С понятием обратной матрицы можно познакомиться в рекомендуемой литературе.

2 – ой учебный вопросРЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ

УРАВНЕНИЙ МЕТОДОМ ГАУССА

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

Систематлинейных уравнений спнеизвестными имеет вид:

x1,x2, …,xn– неизвестные.

aij- коэффициенты при неизвестных.

bi- свободные члены (или правые части)

Система линейных уравнений называетсясовместной, если она имеет решение, инесовместной, если она не имеет решения.

Совместная система называетсяопределенной, если она имеет единственное решение инеопределенной, если она имеет бесчисленное множество решений.

Две совместные системы называютсяравносильными, если они имеют одно и то же множество решений.

К элементарным преобразованиям системы отнесем следующее:

1. перемена местами двух любых уравнений;

2. умножение обеих частей любого из уравнений на произвольное число, отличное от нуля;

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

Элементарные преобразования переводят систему уравнений в равносильную ей.

Элементарные преобразования системы используются в методе Гаусса.

Для простоты рассмотрим метод Гаусса для системы трех линейных уравнений с тремя неизвестными в случае, когда существует единственное решение:

Дана система:

( 1 )

1-ый шаг метода Гаусса.

На первом шаге исключим неизвестноех1из всех уравнений системы (1), кроме первого. Пусть коэффициент. Назовем его ведущим элементом. Разделим первое уравнение системы (1) наа11.Получим уравнение:

( 2 )

где

Исключимх1из второго и третьего уравнений системы (1). Для этого вычтем из них уравнение (2), умноженное на коэффициент прих1(соответственноа21иа31).

Система примет вид:

( 3 )

Верхний индекс (1) указывает, что речь идет о коэффициентах первой преобразованной системы.

2-ой шаг метода Гаусса.

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

( 4 )

где

Из третьего уравнения системы (3) вычтем уравнение (4), умноженное наПолучим уравнение:

Предполагая, чтонаходим

В результате преобразований система приняла вид:

(5)

Система вида (5) называетсятреугольной.

Процесс приведения системы (1) к треугольному виду (5) (шаги 1 и 2) называютпрямым ходом метода Гаусса.

Нахождение неизвестных из треугольной системы называютобратным ходом метода Гаусса.

Для этого найденное значениех3подставляют во второе уравнение системы (5) и находятх2. Затемх2их3подставляют в первое уравнение и находятх1.

В общем случае для системытлинейных уравнений спнеизвестными проводятся аналогичные преобразования. На каждом шаге исключается одно из неизвестных из всех уравнений, расположенных ниже ведущего уравнения.

Отсюда другое называние метода Гаусса –метод последовательного исключения неизвестных.

Если в ходе преобразований системы получается противоречивое уравнение вида0 =b, гдеb¹ 0, то это означает, что система несовместна и решений не имеет.

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

Треугольная системаимеет вид:

Такая система имеет единственное решение, которое находится в результате проведения обратного хода метода гаусса.

Ступенчатая системаимеет вид:

Такая система имеет бесчисленное множество решений. Чтобы найти эти решения, во всех уравнениях системы члены с неизвестнымихk+1, … ,xkпереносят в правую часть. Эти неизвестные называются свободными и придают им произвольные значения. Из полученной треугольной системы находимх1, … ,xk, которые будут выражаться через свободные неизвестные. Подробнее об этом можно узнать в рекомендуемой литературе.

Рассмотренный метод Гаусса легко программируется на ЭВМ и является более экономичным (по числу действий), чем другие методы.

ЗАКЛЮЧЕНИЕ

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

доцент Смирнова А.И.

superbotanik.net

Реферат: Матрицы Метод Гаусса

КОСТРОМСКОЙ ФИЛИАЛ ВОЕННОГО УНИВЕРСИТЕТА РХБ ЗАЩИТЫ

Кафедра «Автоматизации управления войсками»

Только для преподавателей

"Утверждаю"

Начальник кафедры № 9

полковник ЯКОВЛЕВ А.Б.

«____»______________ 2004 г.

доцент СМИРНОВА А.И.

"МАТРИЦЫ. МЕТОД ГАУССА"

ЛЕКЦИЯ № 2 / 3

Обсуждено на заседании кафедры № 9

«____»___________ 2003г.

Протокол № ___________

Кострома, 2003

Cодержание

Введение

1. Действия над матрицами.

2. Решение систем линейных уравнений методом Гаусса.

Заключение

Литература

1. В.Е. Шнейдер и др., Краткий курс высшей математики,том I, гл.2,§6, 7.

2. В.С. Щипачев, Высшая математика, гл. 10, § 1, 7.

ВВЕДЕНИЕ

1-ый учебный вопрос ДЕЙСТВИЯ НАД МАТРИЦАМИ

ОПРЕДЕЛЕНИЕ 1. Прямоугольная таблица из m, n чисел, содержащая m – строк и n – столбцов, вида:

называется матрицей размера m ´ n

Числа, из которых составлена матрица, называются элементами матрицы.

Положение элемента аi j в матрице характеризуются двойным индексом:

первый i – номер строки;

второй j – номер столбца, на пересечении которых стоит элемент.

Сокращенно матрицы обозначают заглавными буквами: А, В, С…

Коротко можно записывать так:

ОПРЕДЕЛЕНИЕ 2. Матрица, у которой число строк равно числу столбцов, т.е. m = n , называется квадратной.

Число строк (столбцов) квадратной матрицы называется порядком матрицы.

ПРИМЕР.

ОПРЕДЕЛЕНИЕ 3. Матрица размера 1 ´ n, состоящая из одной строки, называется матрицей – строкой.

Матрица размера т ´ 1, состоящая из одного столбца, называется матрицей – столбцом.

ОПРЕДЕЛЕНИЕ 4. Нулевой матрицей называют матрицу, все элементы которой равны нулю.

Рассмотрим квадратную матрицу порядка n:

побочная диагональ

главная диагональ

Диагональ квадратной матрицы, идущая от верхнего левого элемента таблицы к правому нижнему, называется главной диагональю матрицы (на главной диагонали стоят элементы вида а i i).

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

Рассмотрим некоторые частные виды квадратных матриц.

1) Квадратная матрица называется диагональной, если все элементы, не стоящие на главной диагонали, равны нулю.

3) Квадратная матрица называется треугольной, если все элементы, расположенные по одну сторону от главной диагонали, равны нулю:

верхняя нижняя

треугольная матрица треугольная матрица

Для квадратной матрицы вводится понятие: определитель матрицы. Это определитель, составленный из элементов матрицы. Обозначается:

Ясно, что определитель единичной матрицы равен 1: ½Е½ = 1

ЗАМЕЧАНИЕ. Неквадратная матрица определителя не имеет.

Если определитель квадратичной матрицы отличен от нуля, то матрица называется невырожденной, если определитель равен нулю, то матрица называется вырожденной.

ОПРЕДЕЛЕНИЕ 5. Матрица, полученная из данной заменой ее строк столбцами с теми же номерами, называется транспонированной к данной.

Матрицу, транспонированную к А, обозначают АТ.

ПРИМЕР.

2 3 3 2

ОПРЕДЕЛЕНИЕ. Две матрицы одного и того же размера называются равными, если равны все их соответственные элементы.

Рассмотрим действия над матрицами.

СЛОЖЕНИЕ МАТРИЦ.

Операция сложения вводится только для матриц одинакового размера.

ОПРЕДЕЛЕНИЕ 7. Суммой двух матриц А = (аi j) и В = (bi j) одинакового размера называется матрица С = (сi j) того же размера, элементы которой равны суммам соответствующих элементов слагаемых матриц, т.е. с i j = a i j + b i j

Обозначается сумма матриц А + В.

ПРИМЕР.

УМНОЖЕНИЕ МАТРИЦ НА ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО

ОПРЕДЕЛЕНИЕ 8. Чтобы умножить матрицу на число k, надо умножить на это число каждый элемент матрицы:

если А= (аi j ), то k · A= (k · a i j )

ПРИМЕР.

СВОЙСТВА СЛОЖЕНИЯ МАТРИЦ И УМНОЖЕНИЯ НА ЧИСЛО

1. Переместительное свойство: А + В = В + А

2. Сочетательное свойство: ( А + В ) + С = А + ( В + С )

3. Распределительное свойство: k · ( A + B ) = k A + k B, где k – число

УМНОЖЕНИЕ МАТРИЦ

Матрицу А назовем с о г л а с о в а н н о й с матрицей В , если число столбцов матрицы А равно числу строк матрицы В , т.е. для согласованных матриц матрица А имеет размер m ´ n , матрица В имеет размер n ´ k . Квадратные матрицы согласованы, если они одного порядка.

ОПРЕДЕЛЕНИЕ 9. Произведением матрицы А размера m ´ n на матрицу В размера n ´ k называется матрица С размера m ´ k, элемент которой аi j , расположенный в i –ой строке и j – ом столбце, равен сумме произведений элементов i – ой строки матрицы А на соответствующие элементы j – столбца матрицы В, т.е.

c i j = a i 1 b 1 j + a i 2 b 2 j +……+ a i n b n j

Обозначим: С = А · В.

Если то

Произведение В ´ А не имеет смысла, т.к. матрицы не согласованы.

ЗАМЕЧАНИЕ 1. Если А ´ В имеет смысл, то В ´ А может не иметь смысла.

ЗАМЕЧАНИЕ 2. Если имеет смысл А ´ В и В ´ А, то, вообще говоря

А ´ В ¹ В ´ А, т.е. умножение матриц не обладает переместительным законом.

ЗАМЕЧАНИЕ 3. Если А – квадратная матрица и Е – единичная матрица того же порядка, то А ´ Е = Е ´ А = А.

Отсюда следует, что единичная матрица при умножении играет роль единицы.

ПРИМЕРЫ. Найти , если можно, А ´ В и В ´ А.

Решение: Матрицы А и В согласованы

Матрицы В и А не согласованы, поэтому В ´ А не имеет смысла.

Отметим, что в результате перемножения двух матриц получается матрица, содержащая столько строк, сколько их имеет матрица–множимое и столько столбцов, сколько их имеет матрица-множитель.

СВОЙСТВА УМНОЖЕНИЯ МАТРИЦ

1. Сочетательное свойство: А ´ ( В ´ С ) = (А ´ В ) ´С

2. Распределительное свойство: (А + В) ´ С = А ´ С + В ´С

Можно показать, что , если А и В – две квадратные матрицы одного порядка с определителями ½ А ½ и ½ В ½, то определитель матрицы С = А ´ В равен произведению определителей перемножаемых матриц, т.е.

½С½ = ½ А ½ ½ В ½

2 – ой учебный вопрос РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ

УРАВНЕНИЙ МЕТОДОМ ГАУССА

Система т линейных уравнений с п неизвестными имеет вид:

x1 , x2, …, xn – неизвестные.

ai j - коэффициенты при неизвестных.

bi - свободные члены (или правые части)

Система линейных уравнений называется совместной, если она имеет решение, и несовместной, если она не имеет решения.

Совместная система называется определенной, если она имеет единственное решение и неопределенной, если она имеет бесчисленное множество решений.

Две совместные системы называются равносильными, если они имеют одно и то же множество решений.

К элементарным преобразованиям системы отнесем следующее:

1. перемена местами двух любых уравнений;

2. умножение обеих частей любого из уравнений на произвольное число, отличное от нуля;

Элементарные преобразования переводят систему уравнений в равносильную ей.

Элементарные преобразования системы используются в методе Гаусса.

Дана система:

( 1 )

1-ый шаг метода Гаусса.

На первом шаге исключим неизвестное х1 из всех уравнений системы (1), кроме первого. Пусть коэффициент . Назовем его ведущим элементом. Разделим первое уравнение системы (1) на а11. Получим уравнение:

( 2 )

где

Исключим х1 из второго и третьего уравнений системы (1). Для этого вычтем из них уравнение (2), умноженное на коэффициент при х1 (соответственно а21 и а31).

Система примет вид:

( 3 )

Верхний индекс (1) указывает, что речь идет о коэффициентах первой преобразованной системы.

2-ой шаг метода Гаусса.

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

( 4 )

где

Из третьего уравнения системы (3) вычтем уравнение (4), умноженное на Получим уравнение:

Предполагая, что находим

В результате преобразований система приняла вид:

(5)

Система вида (5) называется треугольной.

Процесс приведения системы (1) к треугольному виду (5) (шаги 1 и 2) называют прямым ходом метода Гаусса.

Нахождение неизвестных из треугольной системы называют обратным ходом метода Гаусса.

Для этого найденное значение х3 подставляют во второе уравнение системы (5) и находят х2. Затем х2 и х3 подставляют в первое уравнение и находят х1.

В общем случае для системы т линейных уравнений с п неизвестными проводятся аналогичные преобразования. На каждом шаге исключается одно из неизвестных из всех уравнений, расположенных ниже ведущего уравнения.

Отсюда другое называние метода Гаусса – метод последовательного исключения неизвестных.

Если в ходе преобразований системы получается противоречивое уравнение вида 0 = b, где b ¹ 0, то это означает, что система несовместна и решений не имеет.

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

Треугольная система имеет вид:

Ступенчатая система имеет вид:

Такая система имеет бесчисленное множество решений. Чтобы найти эти решения, во всех уравнениях системы члены с неизвестными хk+1, … , xk переносят в правую часть. Эти неизвестные называются свободными и придают им произвольные значения. Из полученной треугольной системы находим х1, … , xk, которые будут выражаться через свободные неизвестные. Подробнее об этом можно узнать в рекомендуемой литературе.

ЗАКЛЮЧЕНИЕ

доцент Смирнова А.И.

www.referatmix.ru

Реферат Метод Гаусса Зейделя

скачать

Реферат на тему:

План:

1 Постановка задачи
2 Метод
3 Условие сходимости
4 Условие окончания
5 Пример алгоритма на с++
6 Пример алгоритма на pascal (для кв. системы)

Введение

Метод Гаусса—Зейделя[1] является классическим итерационным методом решения системы линейных уравнений.

1. Постановка задачи

Возьмём систему: $A\vec{x}=\vec{b}$ , где $A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{array} \right),\quad \vec{b}=\left( \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right)$

Или $\left\{ \begin{array}{rcl} a_{11}x_1 + \ldots + a_{1n}x_n& = & b_{1} \\ & &\\ a_{n1}x_1 + \ldots + a_{nn}x_n & = & b_{n} \end{array} \right.$

И покажем, как её можно решить с использованием метода Гаусса-Зейделя.

2. Метод

Чтобы пояснить суть метода, перепишем задачу в виде:

$\left\{ \begin{array}{lcr} a_{11}x_1 & = &-a_{12}x_2 - a_{13}x_3 -\ldots - a_{1n}x_n + b_1\\ a_{21}x_1 + a_{22}x_2 & = & -a_{23}x_3 - \ldots - a_{2n}x_n + b_2\\ \ldots & &\\ a_{(n-1)1}x_1 + a_{(n-1)2}x_2 +\ldots+ a_{(n-1)(n-1)}x_{n-1} & = & -a_{(n-1)n}x_n + b_{n-1}\\ a_{n1}x_1 + a_{n2}x_2 +\ldots+ a_{n(n-1)}x_{n-1}+ a_{nn}x_n & = & b_n \end{array} \right.$

Здесь в j-м уравнении мы перенесли в правую часть все члены, содержащие xi , для i > j. Эта запись может быть представлена:

$(\mathrm{L} + \mathrm{D} )\vec{x} = -\mathrm{U} \, \vec{x} + \vec{b},$

где в принятых обозначениях D означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы A, а все остальные нули; тогда как матрицы U и L содержат верхнюю и нижнюю треугольные части A, на главной диагонали которых нули.

Итерационный процесс в методе Гаусса-Зейделя строится по формуле $(\mathrm{L} + \mathrm{D} )\vec{x}^{(k+1)} = -\mathrm{U} \vec{x}^{(k)} + \vec{b} ,\quad k = 0, 1, 2, \ldots$ после выбора соответствующего начального приближения $\vec{x}^{(0)}$ .

Метод Гаусса-Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что новые значения $\vec{x}^{(i)}$ используются здесь сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации:

$\left\{\begin{array}{ccccccccccc} {x_{1}}^{(k+1)} &=& c_{12}{x_2^{(k)}} &+& c_{13}x_3^{(k)}&+& {\ldots}&+& c_{1n}{x_n}^{(k)} &+& d_1 \\ {x_{2}}^{(k+1)} &=& c_{21}{x_1^{(k+1)}} &+& c_{23}x_3^{(k)}&+& {\ldots}&+& c_{2n}{x_n}^{(k)} &+& d_2 \\ \ldots & & & & & & & & & & \\ {x_{n}}^{(k+1)} &=& c_{n1}{x_1^{(k+1)}} &+& c_{n2}{x_2^{(k+1)}}&+& {\ldots}&+& c_{n(n-1)}{x_{n-1}}^{(k+1)} &+& d_n \end{array}\right.,$

где $c_{ij}=-\frac{a_{ij}}{a_{ii}},\quad d_i=\frac{b_i}{a_{ii}},\quad i=1,\ldots,n$

Таким образом i-тая компонента (k + 1)-го приближения вычисляется по формуле:

$x_i^{(k+1)}=\sum_{j=1}^{i-1}c_{ij}x_{j}^{(k+1)}+\sum_{j=i+1}^{n}c_{ij}x_{j}^{(k)}+d_i, \quad i=1,\ldots,n$

3. Условие сходимости

Приведём достаточное условие сходимости метода.

4. Условие окончания

Условие окончания итерационного процесса Зейделя при достижении точности $\varepsilon$ в упрощённой форме имеет вид:

$\parallel x^{(k+1)}-x^{(k)}\parallel \le \varepsilon$

Более точное условие окончания итерационного процесса имеет вид

$\parallel Ax^{(k)}-b\parallel \le \varepsilon$

и требует больше вычислений. Хорошо подходит для разреженных матриц.

5. Пример алгоритма на с++

// Условие сходимости bool converge(double *xk, double *xkp) { for (int i = 0; i < n; i++) { if (fabs(xk[i] - xkp[i]) >= eps) return false; } return true; } /* Ход метода, где: a[n][n] - Матрица коэффициентов x[n], p[n] - Текущее и предыдущее решения */ do { for (int i = 0; i < n; i++) { double var = 0; for (int j = 0; j < n; j++) if (j != i) var += (a[i][j] * x[j]); p[i] = x[i]; x[i] = (b[i] - var) / a[i][i]; } } while (!converge(x, p));

6. Пример алгоритма на pascal (для кв. системы)

type ar2d = array [1..50, 1..50] of double; ar1d = array [1..50] of double; procedure seidel(n: byte; e: extended; a: ar2d; b: ar1d; x: ar1d); var i, j: longint; s, v, m: double; begin // Проверка на совместность for i := 1 to n do begin s := 0; for j := 1 to n do if j <> i then s := s + abs(a[i, j]); if s >= abs(a[i, i]) then begin writeln('SLAE is incompatible'); exit end; end; // Сам алгоритм repeat m := 0; for i := 1 to n do begin s := 0; for j := 1 to n do if i <> j then s := s + a[i, j] * x[j]; v := x[i]; x[i] := (b[i] - s) / a[i, i]; m:=abs(x[i])-abs(v); end; until m < e; // Вывод корней writeln('roots: '); for i := 1 to n do writeln('x[', i, ']= ', x[i]:0:4); end;

Примечания

Людвиг Зейдель (1821—1896) — немецкий астроном и математик, Карл Фридрих Гаусс (1777—1855) — немецкий математик, астроном и физик

www.wreferat.baza-referat.ru