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

 

 

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

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Казанский национальный исследовательский технологический университет»

(ФГБОУ ВПО КНИТУ)

Кафедра интеллектуальных  систем и управления информационными ресурсами

 

 

Курсовой проект по дисциплине

«Методы вычислений»

на тему:

«Решение системы линейных уравнений методами простых итераций и прогонки».

 

 

 

 

 

                                                                                                   Проверил: старший преподаватель

                                                                      Гильмутдинов Р.Ф.

                                                                       Выполнила: студентка гр.4311-21

                                                                      Захарова А.А.

 

 

 

Казань 2014г.

 

Содержание

 

 

 

Введение

 

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

Решение систем линейных алгебраических уравнений (СЛАУ) является одной из основных задач линейной алгебры. Эта задача имеет важное прикладное значение при решении научных и технических проблем. Решение систем уравнений, содержит четко сформулированный алгоритм для проведения вычислений.

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

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

    Для написания визуальной программы будут использоваться различные технические и программные средства. В качестве инструмента разработки будем использовать С#,  так как он является языком высокого уровня, имеет высокую скорость работы и для языка есть собственная среда разработки. Для разработки удобной и красивой формы будет использоваться Windows Forms. Не менее популярное и одно из лучших приложений - это  Microsoft Office Word, которое будет использовано для написания текста курсового проекта.

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

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

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

     

 

Глава 1.Теоретическая часть

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

 

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

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

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

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

 

2.  Система линейных алгебраических уравнений

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

         Система m линейных алгебраических уравнений с n неизвестными в линейной алгебре — это система уравнений вида

(1)

 

Здесь  — m количество уравнений, а  — количество неизвестных. x1, x2, …, xn — неизвестные, которые надо определить. a11,a12, …, amn — коэффициенты системы — и b1, b2, … bm — свободные члены — предполагаются известными[1]. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно[2].

Система (1) называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) — совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все её уравнения в тождества.

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения.

Совместная система вида (1) может иметь одно или более решений.

Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).

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

 

 

 

 

3. Метод простой итерации решения СЛАУ

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

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

Возьмём систему линейных уравнений:

, где 

Или

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

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

 

где в принятых обозначениях D означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы A, а все остальные нули; тогда как матрицы  U и  L содержат верхнюю и нижнюю треугольные части A, на главной диагонали которых нули, E — единичная матрица.

Тогда процедура нахождения решения имеет вид:

Или в виде поэлементной формулы:

где k счётчик итерации.

В отличие от метода Гаусса-Зейделя мы не можем заменять на в процессе итерационной процедуры, так как эти значения понадобятся для остальных вычислений. Это наиболее значимое различие между методом Якоби и методом Гаусса-Зейделя решения СЛАУ. Таким образом на каждой итерации придётся хранить оба вектора приближений: старый и новый.

Условие сходимости

Приведем достаточное условие сходимости метода.

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

 

 

Условие остановки

Условие окончания итерационного процесса при достижении точности   в упрощённой форме имеет вид:

 

 

 

4. Метод прогонки

         Метод прогонки или алгоритм Томаса используется для решения систем линейных уравнений вида  , где A — трёхдиагональная матрица.

Система уравнений равносильна соотношению

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

Используя это соотношение, выразим xi-1 и xi через xi+1 и подставим в уравнение (1):

,

где Fi — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать

Отсюда следует:

Из первого уравнения получим:

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

Другим способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению

c надиагональной (наддиагональной) матрицей

.

Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы и вектора , начиная с до

 

И

На втором этапе, для вычисляется решение:

   

Такая схема вычисления объясняет также английский термин этого метода «shuttle».

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

 

5. Алгоритм решения и блок схемы

 

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

Рис.1 Алгоритм решения.

                

Рис2.Блок схемы.

Глава 2. Практическая часть

 

2.1. Реализация алгоритма решения

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

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace курсовая

{

    class СЛАУ

    {

        public double[,] matrix; // создаем матрицу

        public double eps;

        public СЛАУ() { }

        public СЛАУ(int a,int b)// переменные а и b

        {

            matrix=new double[a,b];// матрица а на b

        }

        public double[] метод_простых_итераций()// первый метод простых итераций

        {

            int N = matrix.GetLength(0);

            double[] TempX = new double[N];

            double[,] A = new double[N, N];

            for(int i=0;i<N;i++)

            {

                for (int j = 0; j < N; j++)// условие

                {

                    A[i, j] = matrix[i, j];// равенство матриц

                }

            }

            double[] F = new double[N];

            double[] X = new double[N];

            for (int i = 0; i < N; i++)// условие

            {

                F[i] = matrix[i, N];

                X[i] = F[i] / A[i, i];

            }

            double norm;

            do

            {

                for (int i = 0; i < N; i++)

                {

                    TempX[i] = F[i];

                    for (int g = 0; g < N; g++)

                    {

                        if (i != g)

                            TempX[i] -= A[i,g] * X[g];

                    }

                    TempX[i] /= A[i,i];

                }

                norm = Math.Abs(X[0] - TempX[0]);

                for (int h = 0; h < N; h++)

                {

                    if (Math.Abs(X[h] - TempX[h]) > norm)

                        norm = Math.Abs(X[h] - TempX[h]);

                    X[h] = TempX[h];

                }

            } while (norm > eps);

            return X;

        }

        public double[] Метод_прогонки()// второй метод прогонки

        {

            double m;// переменная m

            int n = matrix.GetLength(0);

            double[] f = new double[n];// присваиваем новые значения

            double[] x = new double[n];

            for (int i = 0; i < n; i++)// условие

            {

                f[i] = matrix[i, n];

                x[i] = 0;

            }

            double[,] A = new double[n, n];// приравниваем

            for (int i = 0; i < n; i++)// цикл

            {

                for (int j = 0; j < n; j++)

                {

                    A[i, j] = matrix[i, j];

                }

            }

            double[] c = new double[n];

            double[] b = new double[n-1];

            double[] a= new double[n-1];

            for (int i = 0; i < n; i++)

            {

                c[i] = A[i, i];

            }

            for (int i = 1; i < n; i++)

            {

                a[i-1] = A[i, i-1];

            }

            for (int i = 0; i < n-1; i++)

            {

                b[i] = A[i, i+1];

            }

            for (int i = 1; i < n; i++)// цикл

            {

                m = a[i-1] / c[i - 1];

                c[i] = c[i] - m * b[i - 1];

                f[i] = f[i] - m * f[i - 1];

            }

 

            x[n - 1] = f[n - 1] / c[n - 1];

 

            for (int i = n - 2; i >= 0; i--)

                x[i] = (f[i] - b[i] * x[i + 1]) / c[i];

            return x;

        }

    }

}

 

2) Программа для создания удобной формы, доступной для любых пользователей.

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

 

namespace курсовая

{

    public partial class Form1 : Form