Решение линейных уравнений методом квадратного корня

Решение линейных уравнений методом квадратного корня

Обсуждение и решение задач по математике, физике, химии, экономике

Часовой пояс: UTC + 3 часа [ Летнее время ]

Введение в анализ

Теория очередей (СМО)

Страница находится по новому адресу

Часовой пояс: UTC + 3 часа [ Летнее время ]

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

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

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

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

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

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

К прямымметодам относятся такие методы, которые в предположении, что вычисления ведутся без округлений, позволяют получить точные значения неизвестных. Они просты, универсальны и используются для широкого класса систем. Однако они не применимы к системам больших порядков (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 вам в помощь!

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

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

Кафедра экономической информатики

по дисциплине «Численные методы»

на тему: «Метод квадратных корней для симметричной матрицы при решении СЛАУ»

1. Математическая постановка задачи

2. Описание программного обеспечения

3. Описание тестовых задач

4. Анализ результатов. Выводы

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

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

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

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

Также данную систему можно записать и в матричном виде:

Тогда мы будем иметь матрицу коэффициентов А:

,

столбец свободных членов уравнений f:

,

и столбец неизвестных х:

.

Чтобы данная СЛАУ имела единственное решение, нужно, чтобы определитель матрицы коэффициентов А не был равен нулю (det(A))¹0.

Данную систему можно решить многими методами. Например, методом Гаусса. Решение этой системы методом Гаусса потребует выполнить

действий,

где n – число неизвестных в уравнении. А это довольно таки трудоемко, особенно при больших порядках числа n.

Еще одним точным методом для решения данных СЛАУ является рассматриваемый в данной работе метод квадратных корней для симметричной матрицы А.

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

метод решение корень симметричная матрица

1. Математическая постановка задачи

Метод квадратных корней используется для решения линейной системы вида Ах=f (1.1), в которой матрица А является симметричной, т.е. а_ij=a_ji , где (i, j = 1, 2, …, n).

Данный метод является более экономным и удобным по сравнению с решением систем общего вида. Решение системы осуществляется в два этапа.

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

где , а .

Перемножая матрицы T¢ и T и приравнивая матрице A, получим следующие формулы для определения t_ij:

(1.3)

После того, как матрица Т найдена, систему (1.1) заменяем двумя эквивалентными ей системами с треугольными матрицами

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

(1.5)

(1.6)

И из этих систем (1.5) и (1.6) последовательно находим

(1.7)

При вычислениях применяется обычный контроль с помощью сумм, причем при составлении суммы учитываются все коэффициенты соответствующей строки.

Заметим, что при действительных a_ij могут получиться чисто мнимые t_ij. Метод применим и в этом случае.

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

Всего метод квадратных корней требует

операций умножения и деления (примерно в два раза меньше, чем метод Гаусса), а также n операций извлечения корня.

2. Описание программного обеспечения

Метод квадратных корней был реализован через функцию function [e,x]=mkk(a,f) , с входными переменными а и f и выходными e и х, где

а – матрица коэффициентов А,

f – столбец свободных членов,

х – столбец найденных решений,

е – столбец ошибок.

Столбец ошибок вычисляется, как Е=А*х-f.

Текст функции на языке MatLab:

f=f’; %столбец f переводим в строку

n=size(a,1); % вычисляем мерность матрицы А

=0) % проверяем, чтобы система имела единственное решение

if (size(f’,1)==n) %проверяем соответствует ли мерность матрицы А мерности вектора f

t=zeros(n); %создаем матрицу элементов T и заполняем ее нулями