Прямые методы решения алгебраических уравнений

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

Дата добавления: 2013-12-23 ; просмотров: 17145 ; Нарушение авторских прав

Методы решения СЛАУ

Методы решения СЛАУ делятся на две группы:

– прямые (точные) методы;

– итерационные (приближенные) методы.

К прямымметодам относятся такие методы, которые в предположении, что вычисления ведутся без округлений, позволяют получить точные значения неизвестных. Они просты, универсальны и используются для широкого класса систем. Однако они не применимы к системам больших порядков (n –1 :

; .

При реализации данного метода стоит проблема нахождения обратной матрицы А –1 , выбора экономичной схемы ее получения и достижения приемлемой точности.

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

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

Посредством первого уравнения системы (2.1) исключается х₁ из последующих уравнений. Далее посредством второго уравнения исключается х₂ из последующих уравнений и т. д. Этот процесс называется прямым ходом Гаусса. Исключение неизвестных повторяется до тех пор, пока в левой части последнего n-го уравнения не останется одно неизвестное х_n:

где a¢_nn и b¢ – коэффициенты, полученные в результате линейных (эквивалентных) преобразований.

Прямой ход реализуется по формулам

(2.6)

где m – номер уравнения, из которого исключается x_k; i – номер столбца исходной матрицы; k – номер неизвестного, которое исключается из оставшихся (n – k) уравнений и обозначает номер уравнения, с помощью которого исключается x_k; a_kk – главный (ведущий) элемент матрицы.

Во время счета необходимо следить, чтобы a_kk ¹ 0. В противном случае прибегают к перестановке строк матрицы.

Обратный ход метода Гаусса состоит в последовательном вычислении x_n, x_n–1, . x₁, начиная с (2.5) по алгоритму:

x_n = b¢ / a¢_nn ; . (2.7)

Точность полученного решения оценивается посредством невязки (2.3). В векторе невязки (r₁, r₂, . r_n) Т отыскивается максимальный элемент и сравнивается с заданной точностью e. Приемлемым решение будет, если r_max Т корня следует рассмотреть новую систему

или ,

где – невязка для исходной системы.

Таким образом, решив линейную систему с прежней матрицей А и новым свободным членом = (e₁, e₂, . e_n) Т , получим поправки (d₁, d₂, . d_n).

Пример решения СЛАУ по методу Гаусса (с точностью до трех знаков). Нужно уточнить корни до 10 –4 :

В результате = 4,67; = 7,62; = 9,05. Невязки равны = −0,02; = 0; = −0,01.

Получено уточнение = −0,0039; = −0,0011; = −0,0025. Следовательно, х₁ = 4,6661; х₂ = 7,6189; х₃ = 9,0475.

Невязки будут равны d₁ = −2×10 –4 ; d₂ = −2×10 –4 ; d₃ = 0.

Модифицированный метод Гаусса. В данном случае, помимо соблюдения требования a_kk ¹ 0, при реализации формул (2.6) накладываются дополнительные требования: ведущий (главный) элемент в текущем столбце в процессе преобразований исходной матрицы должен иметь максимальное по модулю значение, что достигается перестановкой строк матрицы.

Пример. В качестве иллюстрации преимущества модифицированного метода Гаусса рассмотрим систему третьего порядка:

(2.8)

Прямой ход метода Гаусса. Исключаем х₁ из второго и третьего уравнений (2.8). Для этого первое уравнение умножаем на 0,3 и складываем со вторым, а затем умножаем первое уравнение на (–0,5) и складываем с третьим. В результате получаем

(2.8а)

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

Умножив второе уравнение на 25 и сложив с третьим, получим

(2.8б)

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

Подставляя полученное решение [0; –1; 1] в исходную систему (2.8), убеждаемся в его истинности.

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

(2.8в)

Прямой ход метода для системы (2.8в) повторим по аналогичной технологии с исходной системой (2.8):

(2.8г)

После исключения х₂ третье уравнение примет вид (остальные – без изменения):

Выполнив обратный ход, получим

Очевидно, что полученные решения [0; –1; 1] и [–0,35; –1,4; 0,99993] различны. Причиной этого является малая величина ведущего элемента во втором уравнении преобразования (2.8г). Чтобы это исключить, переставим в (2.8г) вторую и третью строки:

º (2.8е)

Система (2.8е) после исключения х₂ из третьего уравнения примет следующий вид:

В данном случае, выполнив обратный ход:

получим решение системы (2.8в) [0; –1; 1], которое в точности совпадает с решением исходной системы.

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

Рассмотрим блок-схему модифицированного метода Гаусса (рис. 2.1). Проведем анализ предложенной схемы на примере системы n = 3 (e = 0,001):

(2.9)

; . (2.9а)

Блок 1. Ввод исходных данных: n – порядок системы, A – матрица коэффициентов при неизвестных, – вектор свободных членов.

Блок 2. Цикл I прямого хода (для k, изменяющегося от единицы до предпоследнего значения, т. е. до n – 1) обеспечивает исключение из главной диагонали матрицы А элемента a_kk = 0 благодаря поиску максимального элемента a_kk в текущем столбце, осуществляемому в блоках 3 — 6 с помощью цикла II.

Далее с помощью цикла III в блоках 7 — 13 выполняется перестановка текущей строки и строки с максимальным элементом в k-м столбце (ее номер р).

Затем реализуются расчеты по формулам (2.6) прямого хода Гаусса в блоках циклов IV и V.

Проведем поблочный анализ в среде рассмотренных циклов I — V на примере (2.9).

Выход из цикла II и вход в цикл III:

В данном случае на диагонали оказался максимальный элемент, поэтому перестановка 2-й и 3-й строк не выполняется.

Выход из цикла III и выполнение блоков 11 – 13:

Свободный член b₂ остается на своем месте.

Вход во вложенный цикл V:

Выход из циклов V и IV и завершение (выход) цикла I.

Выполнение обратного хода метода Гаусса:

В блоках 19 — 24 реализуются формулы (2.7). В блоке 19 из последнего уравнения (2.7) находится значение x_n (n = 3):

Вход в цикл VI (блок 20), в котором значение переменной цикла k изменяется от n – 1 до 1 с шагом (–1):

Вход в цикл VII (блок 22):

Выход из цикла VII в блок 24 цикла VI:

Далее по аналогии:

Выход из последнего цикла VII.

В блоке 25 (цикл опущен) выполняется вывод на экран полученного решения СЛАУ – вектора , т. е. x_i, i = 1, . n. В данном случае (1; 0; 1).

Метод прогонки. Данный метод является модификацией метода Гаусса для частного случая разреженных систем – систем с матрицей трехдиагонального типа (краевая задача дифференциальных уравнений).

Каноническая форма их записи:

a_ix_i–1 + b_ix_i + c_ix_i+1 = d_i; i = ; a₁ = c_n = 0, (2.10)

или в развернутом виде

При этом, как правило, все коэффициенты b_i ¹ 0.

Метод реализуется в два этапа – прямой и обратный ходы.

посредством прогоночных коэффициентов A_i и B_i. Определим алгоритм их вычисления.

Из первого уравнения системы (2.11) находим x₁:

.

. (2.13)

Из второго уравнения системы (2.11) определяем x₂ через x₃, подставляя найденное значение x₁:

. (2.13а)

, где е₂= а₂× А₁ + b₂.

Ориентируясь на соотношения индексов при коэффициентах (2.12) и (2.12а), можно получить эти соотношения для общего случая:

, где е_i = а_i × А_i–1 + b_i (i = 2, 3, . n – 1). (2.14)

Обратный ход.Из последнего уравнения системы (2.11) с использованием (2.12) при i = n – 1:

. (2.15)

Далее посредством (2.12) и прогоночных коэффициентов (2.13), (2.14) последовательно вычисляем x_{n – 1}, x_{n – 2}, . x₁.

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

или хотя бы для одного b_i имеет место строгое неравенство (2.16), деление на ноль исключается и система имеет единственное решение.

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

Схема алгоритма метода прогонки может иметь вид, представленный на рис. 2.2.

Метод квадратного корня. Данный метод используется для решения линейной системы

, (2.17)

Решение системы (2.17) осуществляется в два этапа.

Прямой ход. Преобразование матрицы А и представление ее в виде произведения двух взаимно транспонированных треугольных матриц:

Перемножив S Т и S и приравняв матрице А, получим следующие формулы для определения s_ij:

(2.19)

После нахождения матрицы S систему (2.17) заменяем двумя ей эквивалентными системами с треугольными матрицами (2.18):

. (2.20)

Обратный ход. Записываем системы (2.20) в развернутом виде:

(2.21)

(2.22)

Используя (2.21) и (2.22), последовательно находим:

(2.23)

(2.24)

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

Машинная реализация метода квадратного корня предусматривает его следующую трактовку.

Исходная матрица А системы (2.17) представляется в виде произведения трех матриц:

где S T – транспонированная нижняя треугольная матрица; D – диагональная матрица с элементами d_ii = ±1; S – верхняя треугольная (s_ik = 0, если i > k , причем s_ii > 0).

Выполнение условия s_ii > 0 необходимо для полной определенности разложения. Это и определяет необходимость введения диагональной матрицы D.

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

Пусть А – действительная симметричная матрица:

.

Будем искать S и D в виде

, , d_ii = ±1.

.

Из условия равенства A = S Т D S получим три уравнения:

Из первого уравнения находим

d₁₁ = sign a₁₁; s₁₁ = .

,

т. е. d₂₂ = sign (a₂₂ ); s₂₂ = .

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

Итак, если S Т DS известно, то решение исходной системы сводится к последовательному решению систем:

. (2.24а)

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

d_k = sign;

s_kk = ; (2.25)

s_kj = ;

В (2.25) сначала полагаем k = 1 и последовательно вычисляем

d₁ = sign (a₁₁); s₁₁ =

и все элементы первой строки матрицы S (s_1j, j > 1), затем полагаем k = 2, вычисляем s₂₂ и вторую строку матрицы s_1j для j > 2 и т. д.

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

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

Схема алгоритма метода квадратного корня представлена на рис. 2.3. Значение функции sign(x) равно +1 для всех х > 0 и –1 для всех x

Не нашли то, что искали? Google вам в помощь!

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

Содержание:

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

Метод Крамера

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

Определение: Определитель, составленный из коэффициентов при неизвестных, называется главным определителем системы

Крамер предложил следующий метод решения СЛАУ: умножим главный определитель на для этого умножим все элементы первого столбца на эту неизвестную:

Второй столбец умножим на третий столбец — на -ый столбец — на и все эти произведения прибавим к первому столбцу, при этом произведение не изменится:

Согласно записи СЛАУ первый столбец получившегося определителя представляет собой столбец свободных коэффициентов, т.е.

Определение: Определитель называется первым вспомогательным определителем СЛАУ.

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

31. Для того чтобы найти вспомогательный определитель i, надо в главном определителе СЛАУ заменить столбец i на столбец свободных коэффициентов.

Определение: Полученные выше соотношения называются формулами Крамера. Используя формулы Крамера, находят неизвестные величины Проанализируем полученные формулы:

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

Пример:

Решить СЛАУ методом Крамера

Решение:

Прежде всего, обращаем внимание на то, что в последнем уравнении переменные записаны в неправильном порядке, в этом случае говорят, что СЛАУ записана в ненормализованном виде. Нормализуем СЛАУ, для чего запишем неизвестные в последнем уравнении системы в правильном порядке, чтобы одноименные неизвестные были записаны друг под другом

Найдем главный определитель СЛАУ (раскрываем по первой строке)

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

Воспользуемся формулами Крамера

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

Выполним проверку Отсюда видно, что СЛАУ решена верно.

Матричный способ решения СЛАУ

Для решения СЛАУ матричным способом введем в рассмотрение матрицу, составленную из коэффициентов при неизвестных матpицы-столбцы неизвестных и свободных коэффициентов

Тогда СЛАУ можно записать в матричном виде Матричный способ решения СЛАУ состоит в следующем: умножим слева матричное уравнение на обратную матрицу к матрице А, получим в силу того, что произведение найдем Таким образом, для нахождения неизвестных матричным способом, надо найти обратную к А матрицу после чего надо умножить эту матрицу на матрицу-столбец свободных коэффициентов.

Пример:

Решить СЛАУ матричным способом

Решение:

Введем в рассмотрение следующие матрицы

Найдем матрицу (см. Лекцию № 2): найдем детерминант матрицы А.

Пример:

Решение:

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

Отсюда находим, что х = 1; y = l; z = l.

Метод Гаусса

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

Замечание: В методе Гаусса желательно, чтобы первая строка расширенной матрицы начиналась с единицы.

Обменяем в расширенной матрице первую и вторую строки местами, получим Приведем матрицу к треугольному виду, выполнив следующие преобразования: умножим элементы первой строки на (-2) и прибавим к соответствующим элементам второй строки Разделим все элементы второй строки на (-5), получим эквивалентную матрицу

Умножим элементы первой строки на (—1) и прибавим к соответствующим элементам третьей строки Разделим все элементы третьей строки на (-3), получим Таким образом, эквивалентная СЛАУ имеет вид (напомним, что первый столбец это коэффициенты при неизвестной х, второй — при неизвестной у, третий — при неизвестной z, а за вертикальной чертой находится столбец свободных коэффициентов):

Из первого уравнения находим, что х = 1.

Вывод: Из вышеизложенного материала следует, что вне зависимости от

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

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

Ранг матрицы. Теорема Кронекера-Капелли

Определение: Рангом матрицы называется наивысший порядок отличного от нуля минора этой матрицы.

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

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

Пример:

Найти ранг матрицы

Решение:

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

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

Следствия из теоремы Кронекера — Капелли

Следствие: Если ранг матрицы совместной системы равен числу неизвестных, то система имеет единственное решение (то есть она определенная).

Следствие: Если ранг матрицы совместной системы меньше числа неизвестных, то система имеет бесчисленное множество решений (т.е. она неопределенная).

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

• Скалярное произведение и его свойства
• Векторное и смешанное произведения векторов
• Преобразования декартовой системы координат
• Бесконечно малые и бесконечно большие функции
• Критерий совместности Кронекера-Капелли
• Формулы Крамера
• Матричный метод
• Экстремум функции

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Прямые и итерационные методы.

Часть 2. системЫ линейных

АлгебраичЕских уравнений

Лекция 2

ЦЕЛЬ ЛЕКЦИИ: Определить два класса численных методов (прямые и итерационные); показать, как строятся прямые методы Гаусса, LU-факторизации, Холесского; выполнить оценку их эффективности.

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

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

В дальнейшем будем использовать запись этой системы в компактной форме:

( запись означает, что индекс i изменяется от 1 до n с шагом 1), или в векторном виде

,

где

Предполагается, что матрица неособенная, т. е. , и решение единственно.

Прямые и итерационные методы.

Численные методы решения СЛАУ делятся на две большие группы: прямые и итерационные.

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

,

где k – номер итерации. В действительности итерационный процесс прекращается, как только становится достаточно близким к .

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

Какой класс методов лучше? Однозначно на этот вопрос ответить нельзя. Итерационные методы привлекательнее с точки зрения объема вычислений и требуемой памяти, когда решаются системы с матрицами высокой размерности. При небольших порядках системы используют прямые методы либо прямые методы в сочетании с итерационными методами.

Метод Гаусса.

В методе Гаусса линейная система

решается в два этапа. На первом этапе система преобразуется к виду (см. рис. 2.1)

,

Рис. 2.1. Структура системы и портрет ее ненулевых элементов до (а) и после (б)

прямого хода Гаусса

где – верхняя треугольная матрица с единичной диагональю (это так

называемый прямой ход Гаусса). На втором этапе (обратный ход Гаусса) решается система . Рассмотрим эти этапы подробнее.

Прямой ход. Прямой ход Гаусса состоит из n шагов.

Первый шаг. Полагаем, что и разделим на него первое уравнение. Перепишем систему с учетом этого преобразования:

Умножим первое уравнение на и вычтем его из i-го уравнения преобразованной системы:

Обозначим . Получим

Второй шаг. На втором шаге из системы

исключается аналогичным образом:

K-й шаг. Запишем общий вид преобразованной системы после k-го шага прямого хода Гаусса:

Проиллюстрируем, как меняется матрица системы в процессе прямого хода Гаусса на примере системы четвертого порядка (рис. 2.2; ненулевые элементы матрицы обозначены крестиками).

Рис. 2.2. Преобразование матрицы системы 4-го порядка на прямом ходе Гаусса

Оценим количество длинных операций (умножений и делений) на первом шаге прямого хода Гаусса. Преобразование первого уравнения требует n таких операций. Преобразование остальных n-1 уравнений – n(n-1) операций умножения и деления. Таким образом, первый шаг выполняется за длинных операций. Рассуждая по аналогии, нетрудно найти затраты на остальных n-1 шагах. Суммарные затраты прямого хода Гаусса определяются в итоге рядом

.

Последняя оценка имеет место для n>>1.

Обратный ход. Запишем систему, решаемую на обратном ходе, в координатном виде

Запись означает, что индекс k изменяется от значения n-1 до 1 с шагом 1.

Требуемое число длинных операций на обратном ходе

Приближенная оценка справедлива для n>>1.

Общие затраты метода Гаусса:

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

Дата добавления: 2015-11-24 ; просмотров: 2530 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ