40830

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

Лекция

Информатика, кибернетика и программирование

Основные понятия и определения Выделяют четыре основные задачи линейной алгебры: решение СЛАУ вычисление определителя матрицы нахождение обратной матрицы определение собственных значений и собственных векторов матрицы. Задача отыскания решения СЛАУ с n неизвестными одна из наиболее часто встречающихся в практике вычислительных задач так как большинство методов решения сложных задач основано на сведении...

Русский

2013-10-22

1 MB

102 чел.

ТЕМА 2. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ                                        АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СЛАУ)

2.1. Основные понятия и определения

Выделяют четыре основные задачи линейной алгебры: решение СЛАУ, вычисление определителя матрицы, нахождение обратной матрицы, определение собственных значений и собственных векторов матрицы.

Задача отыскания решения СЛАУ с n неизвестными – одна из наиболее часто встречающихся в практике вычислительных задач, так как большинство методов решения сложных задач основано на сведении их к решению некоторой последовательности СЛАУ.

Обычно СЛАУ записывается в виде

    или коротко

  .   (2.1)

Здесь А и  заданы, требуется найти *, удовлетворяющий (2.1).

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

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

Методы решения СЛАУ делятся на прямые и итерационные.

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

Наибольшее распространение среди прямых методов получили метод Гаусса для СЛАУ общего вида, его модификация для трехдиагональной матрицы – метод прогонки и метод квадратного корня для СЛАУ с симметричной матрицей.

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

Итерационные методы выгодны для систем большого порядка n > 1000, а также для решения плохо обусловленных систем. Многообразие итерационных методов решения СЛАУ объясняется возможностью большого выбора рекуррентных последовательностей, определяющих метод. Наибольшее распространение среди итерационных методов получили одношаговые методы простой итерации и Зейделя с использованием релаксации.

Для контроля полезно найти невязку полученного решения :

если D велико, то это указывает на грубую ошибку в расчете.

Ниже приведено описание алгоритмов указанных методов решения СЛАУ.

2.2. Прямые методы решения СЛАУ

Метод Гаусса (MG)

Метод основан на приведении с помощью преобразований, не меняющих решение, исходной СЛАУ (2.1) с произвольной матрицей к СЛАУ с верхней треугольной матрицей вида

    .     (2.2)

Этап приведения к системе с треугольной матрицей называется прямым ходом метода Гаусса.

Решение системы с верхней треугольной матрицей (2.2), как легко видеть, находится по формулам, называемым обратным ходом метода Гаусса:

  (2.3)

 Прямой ход метода Гаусса осуществляется следующим образом: вычтем из каждого m-го уравнения (m = 2 ... n) первое уравнение, умноженное на  и вместо m-го уравнения оставим полученное. В результате в матрице системы исключаются все коэффициенты первого столбца ниже диагонального. Затем, используя второе полученное уравнение, аналогично исключим элементы второго столбца (m = 3 ... n) ниже диагонального и т.д. Такое исключение называется циклом метода Гаусса. Проделывая последовательно эту операцию с расположенными ниже k-го уравнениями (k=1, 2, ..., n-1), приходим к системе вида (2.2). При указанных операциях решение СЛАУ не изменяется.

На каждом k-м шаге преобразований прямого хода элементы матриц изменяются по формулам прямого хода метода Гаусса:

    (2.4)

Элементы  называются главными. Заметим, что если в ходе расчетов по данному алгоритму на главной диагонали окажется нулевой элемент , то произойдет сбой в ЭВМ. Для того чтобы этого избежать, следует каждый цикл по k начинать с перестановки строк: среди элементов k-го столбца  находят номер p главного, т.е. наибольшего по модулю, и меняют местами строки k и p. Такой выбор главного элемента значительно повышает устойчивость алгоритма к ошибкам округления, так как в формулах (2.4) при этом производится умножение на числа , меньшие единицы, и ошибка, возникшая ранее, уменьшается.

Схема алгоритма с выбором главного элемента приведена на рис.2.2.

Проиллюстрируем метод Гаусса на решении СЛАУ 3-го порядка:

 Первый цикл: вычтем из второго уравнения первое, умноженное на , а из третьего – первое, умноженное на  получим



 Второй цикл: вычтем из третьего уравнения второе, умноженное на        a3,2/a2,2 = 0,5; получим систему с треугольной матрицей вида (2.2):

 Обратный ход: из последнего уравнения находим , подставляя во второе, находим , подставляя в первое, находим .

Таким образом, получен вектор решения

Метод прогонки (MP)

Многие задачи (например решение дифференциальных уравнений второго порядка) приводят к необходимости решения СЛАУ с трехдиагональной матрицей:

  .  (2.5)

или коротко эту систему записывают в виде

         (2.6)

В этом случае расчетные формулы метода Гаусса значительно упрощаются. После исключения поддиагональных элементов в результате прямого хода метода Гаусса и последующего деления каждого уравнения на диагональный элемент систему (2.5) можно привести к виду

  .  (2.7)

При этом формулы прямого хода для вычисления  имеют вид

    (2.8)

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

       (2.9)

Расчетные формулы (2.8), (2.9) получили название «метод прогонки». Достаточным условием того, что в формулах метода прогонки не произойдет деления на ноль и расчет будет устойчив относительно погрешностей округления, является выполнение неравенства  (хотя бы для одного i должно быть строгое неравенство).

Схема алгоритма метода прогонки представлена на рис. 2.3.

Метод квадратного корня (MQ) 

Метод предназначен для решения СЛАУ с симметричной матрицей. Этот метод основан на представлении такой матрицы в виде произведения трех матриц:  где D – диагональная с элементами di=1;  S – верхняя треугольная ( если i>k, причем ); – транспонированная нижняя треугольная. Матрицу S можно по аналогии с числами трактовать как корень квадратный из матрицы A, отсюда и название метода.

Если S и D известны, то решение исходной системы  сводится к последовательному решению трех систем – двух треугольных и одной диагональной:

    .    (2.10)

Здесь .

Решение систем (2.10) ввиду треугольности матрицы S осуществляется по формулам, аналогичным обратному ходу метода Гаусса:

Нахождение элементов матрицы S (извлечение корня из А) осуществляется по рекуррентным формулам:

    ;

        (2.11)

    

В этих формулах сначала полагаем k=1 и последовательно вычисляем  и все элементы первой строки матрицы , затем полагаем k=2, вычисляем  и вторую строку  для j>2 и т.д.

Метод квадратного корня почти вдвое эффективнее метода Гаусса, т.к. полезно использует симметричность матрицы.

Схема алгоритма метода квадратного корня представлена на рис.2.4. Функция sign(x) возвращает –1 для всех x<0 и +1 для всех x>0.



Проиллюстрируем метод квадратного корня, решая систему трех уравнений:

   .   (2.12)

Нетрудно проверить, что матрица A есть произведение двух треугольных матриц (здесь ):

.

Исходную систему запишем в виде

.

Обозначим

.

Тогда для вектора  получим систему :

.

Зная , решаем систему :

.

2.3. Итерационные методы решения СЛАУ

Метод простой итерации (MI)

В соответствии с общей идеей итерационных методов (см. подразд. 1.5) исходная система (2.1) должна быть приведена к виду, разрешенному относительно :

   ,      (2.13)

где G – матрица;  – столбец свободных членов.

При этом решение (2.13) должно совпадать с решением (2.1). Затем строится рекуррентная последовательность первого порядка в виде

.

Для начала вычислений задается некоторое начальное приближение  (например , для окончания – некоторое малое . Получаемая последовательность будет сходиться к точному решению, если норма матрицы  (см. подразд. 1.5).

Привести исходную систему к виду (2.13) можно различными способами, например:

Здесь E – единичная матрица; a – некоторый параметр, подбирая который можно добиться, чтобы

В частном случае, если исходная матрица A имеет преобладающую главную диагональ, т.е. , то преобразование (2.1) к (2.13) можно осуществить просто, решая каждое i-е уравнение относительно . В результате получим следующую рекуррентную формулу:

  ,    (2.14)

   .

Схема алгоритма представлена на рис. 2.5.

Приведем пример решения методом простой итерации следующей системы трех уравнений:

         (2.15)

Преобразуем ее к виду (2.13), для чего из первого уравнения выразим , из второго  и из третьего  и получим рекуррентную формулу

    (2.16)

Зададим начальное приближение , подставим в правую часть (k = 1), получим :  ().

Подставляя полученные значения снова в (2.16) (k = 2), получим :



= (1.075; 1.3; 1.175).

Вычислим погрешность на второй итерации:

Если , то процесс продолжаем.

Метод Зейделя (MZ)

Метод Зейделя является модификацией метода простой итерации. Суть его состоит в том, что при вычислении очередного приближения  в формуле (2.14) используются вместо  уже вычисленные ранее  т.е. (2.14) преобразуется к виду

      (2.17)

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

Схема алгоритма аналогична схеме метода простой итерации (см. рис.2.5), если x0j заменить на xj и убрать строки x0i=1,  x0i=xi.

Для иллюстрации решим систему (2.15) методом Зейделя. Разрешая ее, относительно , аналогично (2.16) получаем рекуррентную формулу (2.17) вида

         (2.18)

Зададим, как и в методе простой итерации, начальное условие , подставим в первое уравнение, получаем  При вычислении  это значение сразу используем: , аналогично  получаем . Для второй итерации:

  

 Погрешность после двух итераций  меньше, чем в методе простой итерации.

2.4. Понятие релаксации

Методы простой итерации и Зейделя сходятся примерно так же, как геометрическая прогрессия со знаменателем . Если норма матрицы G близка к 1, то сходимость очень медленная. Для ускорения сходимости используется метод релаксации. Суть его в том, что полученное по методу простой итерации или Зейделя очередное значение  пересчитывается по формуле

    .     (2.19)

Здесь 0 <   2параметр релаксации.

Если < 1 – нижняя релаксация, если > 1 – верхняя релаксация. Параметр  подбирают так, чтобы сходимость метода достигалась за минимальное число итераций.

Схема алгоритма на рис. 2.5 выполнена с использованием релаксации.

2.5. Варианты заданий

Составить программу решения СЛАУ порядка n и решить систему линейных уравнений пятого порядка с трехдиагональной симметричной матрицей вида

.

Значения q и d заданы в табл. 2.1.  

В вариантах, использующих прямые методы вычислить невязку (см.            подразд. 2.1).

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

                                             Таблица 2.1

№ вар.

Mетод

d

q

e

1

MG

–1

–4.25

2

MI

1

–3.17

10–3

3

MQ

–2

–3.23

4

MZ

2

–2.57

10–4

5

MP

–3

–4.67

6

MI

3

–2.23

10–4

7

MG

–4

–2.75

8

MI

4

–2.25

10–4

9

MQ

–5

–2.85

10

MZ

5

–2.24

10–5

11

MP

–6

–3.83

12

MZ

6

–2.17

10–4

13

MG

–7

–2.86

14

MI

7

–3.14

10–3

15

MQ

8

4.88

2.6. Контрольные вопросы

1. Что понимается под корректностью СЛАУ?

2. Решите по методу Гаусса заданную систему из трех уравнений.

3. В чем суть метода квадратного корня?

4. Когда используются методы прогонки и квадратного корня?

5. Решите заданную систему трех уравнений методом простой итерации и методом Зейделя.

6. Для чего нужна релаксация? Ее суть.

PAGE  23


 

А также другие работы, которые могут Вас заинтересовать

66743. Прагматика единиц, выражающих статическое состояние в древнерусском и древнечешском языках 1.07 MB
  Интересным в этом плане нам представляется проследить формирование в данных славянских языках категории состояния то есть специфической группы знаменательных слов которые выражают физическое или психическое состояние человека обозначают природные явления а в предложении выполняют исключительно предикативную функцию.
66746. ГРАЖДАНСКО-ПРАВОВАЯ ОТВЕТСТВЕННОСТЬ ЗА НАРУШЕНИЕ СОГЛАШЕНИЯ О РАЗДЕЛЕ ПРОДУКЦИИ (СРП) 1 MB
  Поскольку соглашение о разделе продукции далее СРП является относительно новой для нашей страны договорной формой регулирования отношений то необходимо более полное изучение и использование огромного накопленного мировым сообществом...
66747. Оценка стоимости брэнда 838.5 KB
  Оценка стоимости брэнда является насущной проблемой корпораций которая подстерегает их и во взаимоотношениях с внешними контрагентами и в процессе внутреннего управления. Недооценка брэнда может грозить враждебным поглощением а переоценка неэффективностью расходования ресурсов компании и уменьшением ее стоимости.
66748. ОБРАЗ ВОДЫ И ВОДНОЙ СТИХИИ В СИСТЕМЕ ГОГОЛЕВСКОЙ ХУДОЖЕСТВЕННОЙ АРХАИКИ (НА МАТЕРИАЛЕ ЦИКЛА «ВЕЧЕРА НА ХУТОРЕ БЛИЗ ДИКАНЬКИ») 1021 KB
  Гоголя в связи с главными моментами его душевного развития и параллельно с этим излагает историю русской повести и драмы с конца XVIII в. Объектом исследования являются повести Н. Сохраняя древнюю архетипическую память эти образы развивают авторскую идею в каждой отдельно взятой повести...
66749. УГОЛОВНАЯ ОТВЕТСТВЕННОСТЬ СОТРУДНИКОВ УГОЛОВНО-ИСПОЛНИТЕЛЬНОЙ СИСТЕМЫ РОССИИ ЗА НЕПРАВОМЕРНОЕ ПРИМЕНЕНИЕ ФИЗИЧЕСКОЙ СИЛЫ, СПЕЦИАЛЬНЫХ СРЕДСТВ И ОРУЖИЯ 636.67 KB
  Анализ развития законодательной регламентации уголовной ответственности сотрудников УИС России за неправомерное применение физической силы специальных средств и оружия на различных исторических этапах. Сравнительно-правовой аспект законодательной регламентации уголовной ответственности...