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

1 2 3 4 5

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

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

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

Курс: "Численные методы"

Пояснительная записка к курсовой работе на тему

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

Факультет: Бизнеса

Преподаватель: Сарычева О. М.

Новосибирск, 2010

Содержание

1. Введение

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

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

3.1 Общие сведения

3.2 Функциональное назначение программы

3.3 Вызов и загрузка программы

3.4 Входные данные

3.5 Выходные данные

3.6 Описание алгоритмов

3.6.1 Программный модуль metod1.m

3.6.2 Программный модуль metod2.m

3.7 Используемые программные и технические средства

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

5. Анализ результатов счета, выводы

6. Заключение

Приложения

Список литературы

Введение

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

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

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

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

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

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

Исследовать метод простой итерации для решения систем линейных алгебраических уравнений, а именно: влияние способа перехода от системы F(x)=x к системе x= (x) на точность полученного решения, скорость сходимости метода, время счета, число операций.

Описание метода

Пусть дана система линейных алгебраических уравнений в виде Ax=b (2.2.1).

Пусть (2.2.1.) приведена каким-либо образом к виду x=Cx+f (2.2.2), где C - некоторая матрица, f - вектор-столбец. Исходя из произвольного вектора

x⁰₁

x⁽⁰⁾= x⁰₂

x⁰₃

строим итерационный процесс x⁽^k⁺¹⁾=Cx⁽^k⁾+f (k=0,1,2,3,…) или в развернутой форме

x₁^(k+1)= c₁₁x₁^(k)+ c₁₂x₂^(k) + …+ c_1nx_n^(k) + f₁, (2.2.3)

x_n^(k+1)= c_n1x₁^(k)+ c_n2x₂^(k) + …+ _1nnx_n^(k) + f_n.

Производя итерации, получим последовательность векторов x⁽¹⁾, x⁽²⁾,…, x⁽^k⁾,… Доказано, что если элементы матрицы C удовлетворяют одному из условий

(i=1,2,…,n) (2.2.4)

(j=1,2,…,n) (2.2.5),

то процесс итерации сходится к точному решению системы x при любом начальном векторе x⁽⁰⁾, то есть

x= x⁽^k⁾.

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

| x_i - x_i⁽^k⁾ | | x_i⁽^k⁾- x_i⁽^k^-1)|, (2.2.4')

если выполнено условие (2.2.4), или

| x_i - x_i⁽^k⁾ | | x_i⁽^k⁾- x_i⁽^k^-1)|, (2.2.5')

если выполнено условие (2.2.5). Эти оценки можно еще усилить соответственно так:

max | x_i - x_i⁽^k⁾ | | x_i⁽^k⁾- x_i⁽^k^-1)|, (2.2.4'')

или

| x_i - x_i⁽^k⁾ | | x_i⁽^k⁾- x_i⁽^k^-1)|. (2.2.5'')

Процесс итераций заканчивают, когда указанные оценки свидетельствуют о достижении заданной точности.

Начальный вектор x⁽⁰⁾ может быть выбран, вообще говоря, произвольно. Иногда берут x⁽⁰⁾=f. Однако, наиболее целесообразно в качестве компонент вектора x⁽⁰⁾ взять приближенные значения неизвестных, полученные грубой прикидкой.

Приведение системы (2.2.1) к виду (2.2.2) можно осуществить различными способами. Важно только, чтобы выполнялось одно из условий (2.2.4) или (2.2.5). Ограничимся рассмотрением двух таких способов.

Первый способ. Если диагональные элементы матрицы А отличны от нуля, то есть

a_ii0 (i=1,2,…,n),

то систему (2.2.1) можно записать в виде

x₁= (b₁ - a₁₂ x₂ - … - a_1n x_n),

x₂= (b₂ - a₂₁ x₁ - a₂₃ x₃-… - a_2n x_n), (2.2.6)

x_n= (b_n - a_n1 x₁ - … - a_{n n-1} x_n-1).

В этом случае элементы матрицы С определяются следующим образом:

(i j), c_ii=0,

и тогда условия (2.2.4) и (2.2.5) соответственно приобретают вид

(i=1,2,…,n), (2.2.7)

(j=1,2,…,n). (2.2.8)

Неравенства (2.2.7), (2.2.8) будут выполнены, если диагональные элементы матрицы А удовлетворяют условию

(i=1,2,…,n), (2.2.9)

то есть если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Второй способ позволяет записать систему (2.2.1) в виде

x₁= b₁ - (a₁₁-1)x₁ - a₁₂ x₂ - … - a_1n x_n,

x₂= b₂ - a₂₁ x₁ -(a₂₂ -1)x₂-… - a_2n x_n, (2.2.10)

x_n= b_n - a_n1 x₁ - a_n2 x₂ - … -(a_nn -1)x_n.

и пояснений не требует.

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

Общие сведения

Данное программное обеспечение представлено в виде двух основных программных модулей (файлы metod1.m и metod2.m) и четырех вспомогательных модулей (файлы system_a.m, system_b.m, x0.m и x_ok.m).