Войти на сайт

или
Регистрация

Навигация


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

11265
знаков
1
таблица
9
изображений

Министерство науки и образования Украины

Сумской государственный университет

Механико-математический факультет

Кафедра информатики

“Точные методы численного решения систем линейных алгебраических уравнений” Сумы 2006

Содержание

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

1. Введение

2. Точные методы решения СЛАУ

3. Практическая реализация метода Халецкого

3.1 Программа на языке Pascal

3.2 Решение в Excel

Заключение

Литература

Приложение


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

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


1. Введение

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

Для того чтобы система линейных алгебраических уравнений имела решение, необходимо и достаточно, чтобы ранг основной матрицы был равен рангу расширенной матрицы. Если ранг основной матрицы равен рангу расширенной матрицы и равен числу неизвестных, то система имеет единственное решение. Если ранг основной матрицы равен рангу расширенной матрицы, но меньший числа неизвестных, то система имеет бесконечно решений.

Пример системы линейных уравнений:

Или в матричном виде: ,

где матрица коэффициентов системы;

 - вектор неизвестных; - вектор свободных членов.

2. Точные методы решения СЛАУ

Метод главных элементов.

Пусть дана система линейных алгебраических уравнений. Рассмотрим расширенную матрицу, состоящую из коэффициентов системы a[i,j] и свободных членов b[i]. Метод главных элементов - это обобщение метода исключения переменных (метода Гаусса). Обозначим матрицу, состоящую из коэффициентов при неизвестных и столбца свободных членов исходной системы за M.

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

Вычисляются множители:

Далее производим следующие преобразования: к каждой неглавной строке прибавим главную строку, умноженную на соответствующий множитель для этой строки. В результате мы получим матрицу, у которой q-й столбец состоит из нулей. Отбросим этот столбец и главную p-ю строку, получим новую матрицу с меньшим на единицу числом строк и столбцов. Над матрицей повторяем те же операции, после чего получаем матрицу и т.д. Таким образом, мы построим последовательность матриц

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

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

Метод квадратных корней

Метод квадратных корней разработан для решения линейных систем с симметричной матрицей коэффициентов. Пусть дана линейная система

Ax=b,

где или (симметрическая матрица).

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

A=T'*T,

Перемножим матрицы T' и T. Из T' i-ю строку из T j-тый столбец, получим следующие уравнения:

Последовательно находим:

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

Решим систему T'*y=b. Запишем её в развёрнутом виде:

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


Решаем систему T*x=y, записав её в развёрнутом виде:

Решение имеет вид

Прямым ходом с помощью формул вычисляются t[i,j] и y[i], обратным ходом по формуле находятся x[i].Текущий контроль прямого хода осуществляется с помощью так называемых "контрольных сумм", которые представляют собой сумму элементов строк матрицы исходной системы, включая свободные члены. Если над контрольными суммами в каждой строке проделывать те же операции, что и над остальными элементами этой строки, то при отсутствии ошибок в вычислениях сумма преобразованных элементов равна преобразованной сумме. Обратный ход контролируется следующим образом: если в формулах для определения вместо столбца свободных членов взять соответствующие элементы из столбца контрольных сумм, то получим новые неизвестные, которые обозначим'.

При отсутствии ошибок '-=1.

Метод Халецкого Запишем систему линейных уравнений в матричном виде: ,

где A=[aij] – квадратная матрица порядка n и

,  - векторы-столбцы.

Представим матрицу A в виде произведения нижней треугольной матрицы B=[bij] и верхней треугольной матрицы C=[cij] с единичной диагональю , где

 и .

Тогда элементы bij и cij определяются по формулам

 и

Отсюда искомый вектор x может быть вычислен из уравнений  и .

Так как матрицы B и C – треугольные, то системы легко решаются:

 и

Из этих двух формул видно, что числа yi выгодно вычислять вместе с коэффициентами cij. Этот метод получил название схемы Халецкого. В схеме применяется обычный контроль с помощью сумм. Если матрица A – симметрическая aij=aji, то

 

Пример. Решить систему

Решение.

В первый раздел таблицы впишем матрицу коэффициентов системы, ее свободные члены и контрольные суммы. Далее так как  , то первый столбец из раздела 1 переносится в первый столбец раздела II. Чтобы получить первую строку раздела II, делим все элементы первой строки раздела I на элемент, в нашем случае на 3.

Имеем:


;

;

;

;

.

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

;

;

.

Далее определяя по формулам, заполняем вторую сетку для раздела II:

Затем переходим к третьему столбцу, вычисляя его элементы  и  по формулам и т.д., пока не будет заполнена вся таблица раздела II. Таким образом, заполнение раздела II происходит способом “елочки”: столбец - строка, столбец - строка и т.д.

В разделе Ш, пользуясь формулами, определяем  и .

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

 

 

 

I

3 1 -1 2 6 11
I

-5 1 3 -4 -12 -17
I

2 0 1 -1 1 3
I

1 -5 3 -3 3 -1
II

│1

3│1 0.333333 -0.333333 0.666667 2 3.666667
II

│1

-5 2.666667│1 0.5 -0.25 -0.75 0.5
II

│1

2 -0.666667 2│1 -1.25 -1.75 -2
II

│1

1 -5.333333 6 2.5│1 3 4
III        

        2 1
III        

        -0.75 -1
III         y3

        -1.75 2
III         y4

        3 3

 



Информация о работе «Точные методы численного решения систем линейных алгебраических уравнений»
Раздел: Математика
Количество знаков с пробелами: 11265
Количество таблиц: 1
Количество изображений: 9

Похожие работы

Скачать
24924
0
20

... , но выбор перехода к системе x=(x) зависит от типа конкретной решаемой системы линейных алгебраических уравнений. 6. Заключение В данной курсовой работе был реализован метод простой итерации для решения систем линейных алгебраических уравнений в виде двух программ, каждая из которых использует свой собственный способ перехода от системы вида F(x)=x к системе вида x=(x). Вообще говоря, ...

Скачать
15393
0
10

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

Скачать
8991
0
13

... образом, исходная система может быть представлена в виде: , откуда получаем: x =1, y = 2, z = 3. 2. Математические и алгоритмические основы решения задачи 2.1 Описание метода Метод Гаусса - классический метод решения системы линейных алгебраических уравнений (СЛАУ). Состоит в постепенном понижении порядка системы и исключении неизвестных. Пусть исходная система выглядит следующим ...

Скачать
22411
1
13

... шаг интегрирования ; tp – время интегрирования трех точечным методом прогноза и коррекции , ta – время интегрирования по методу Адамса-Башфорта , NU – массив начальных условий . Данная процедура способна производить решения систем линейных дифференциальных уравнений произвольного размера , на произвольном промежутке времени интегрирования . Вычисленные данные записываются в файлы prandcom*.df . ...

0 комментариев


Наверх