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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 и заполняем ее нулями

Контрольная работа: Метод квадратных корней

Система линейных алгебраических уравнений – математическая модель, которая описывает состояние равновесия экономического объекта, которое называется установившимся режимом или статикой объекта. Экономическая статика изучает допустимые и рациональные состояния экономического объекта.

Пусть дана система n линейных алгебраических уравнений с n неизвестными

или в матричной форме

— столбец свободных членов и столбец неизвестных соответственно.

Если матрица А неособенная, т.е.

то система (1.1) имеет единственное решение. В этом случае решение системы (1.1) с теоретической точки зрения не представляет труда. Значения неизвестных x_i (i=1,2,…n) могут быть получены по известным формулам Крамера

крамер квадратный корень матрица

где матрица A_i получается из матрицы А заменой ее i-го столбца столбцом свободных членов.

Но такой способ решения линейной системы с n неизвестными приводит к вычислению n + 1 определителей порядка n, что представляет собой весьма трудоемкую операцию при сколько-нибудь большом числе n.

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

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

Приближенными методами называются такие методы, которые даже в предположении, что вычисления ведутся без округлений, позволяют получить решение системы (x₁ , x₂ , …, x_n ) лишь с заданной точностью. Точное решение системы в этих случаях может быть получено теоретически как результат бесконечного процесса. К приближенным методам относятся метод простой итерации, метод Зейделя и др. Каждый из этих методов не всегда является сходящимся в применении к конкретному классу систем линейных уравнений.

Данная контрольная работа имеет следующую структуру: в начале рассматривается математическая постановка задачи для метода квадратных корней при решении систем линейных алгебраических уравнений. Затем производится реализация данного метода с помощью вычислительных средств ЭВМ, а именно прикладной программой Matlab 6.5. На примере реализации нескольких тестовых задач проводится анализ точности данного метода, а именно когда наиболее эффективно применять метод квадратных корней при решении систем линейных алгебраических уравнений. Анализ проводится на основе матрицы А (ее мерности, разреженности, обусловленности. Результаты, полученные на основе метода квадратных корней, приведены в конце данной работы. Также в работе представлен графический материал. По окончании проведения исследования работа завершается логическим заключением.

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

у которой матрица А симметрическая, т.е.

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

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

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

А = Т¢ Т,

.

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

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

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

Отсюда последовательно находим

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

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

Для изучения данного метода было выбрано программное обеспечение: Matlab 6.5, в операционной системе WindowsXPProfessional. На этапе проектирования была создана программа Square (‘квадрат’). Входными переменными для данной программы является матрица A и соответствующая ей матрица B. Результатом выполнения данной программы является матрица X (выходная переменная), которая является решением системы линейных алгебраических уравнений.

Ниже описан алгоритм реализации метода квадратных корней на языке программирования в среде Matlab 6.5:

A=input(‘Введите матрицу A=’);

if i * — b (x * — полученное решение). Для этого рассмотрим разного рода матрицы:

— влияние мерности матрицы А;

Рассмотрим матрицы мерности 2´2, 3´3, 4´4 и 5´5. Зададим матрицу мерностью 2´2:

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

X =

ε =

Зададим матрицу размерностью 3´3:

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

X =

ε =

Зададим матрицу размерностью 4´4:

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

X =

ε =

Зададим матрицу размерностью 5´5:

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

X =

ε =

Сравним полученные результаты, для этого проанализируем точность полученного решения. Результат мы можем оценить двумя способами и , где E – матрица, полученная в результате подстановки найденного решения в систему линейных алгебраических уравнений: Е=A*x-b. Проиллюстрируем результаты графически. Для этого была разработана программа в среде Matlab 6.5.