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

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

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

· точные методы, представляющие собой конечные алгоритмы для вычисления корней системы (решение систем с помощью обратной матрицы, правило Крамера, метод Гаусса и др.),

· итерационные методы, позволяющие получить решение системы с заданной точностью путем сходящихся итерационных процессов (метод итерации, метод Зейделя и др.).

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

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

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод известен в различных вариантах уже более 2000 лет. Метод Гаусса -- классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.

Строго говоря, описываемый выше метод правильно называть методом "Гаусса-Жордана" (Gauss-Jordan elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г.). Также интересно заметить, что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).

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

Задача нахождения корня уравнения f(x) = 0 итерационным методом состоит из двух этапов:

· отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

· уточнение приближенных корней - доведение их до заданной степени точности.

Определенным интегралом функции f(x), взятом в интервале от a до b, называется предел, к которому стремится интегральная сумма при стремлении всех промежутков ?x_i к нулю. Согласно правилу трапеций, необходимо заменить график функции F(x) прямой, проходящей через две точки (х₀,у₀) и (х₀+h,у₁), и вычислить значение элемента интегральной суммы как площадь трапеции:.



1.РЕШЕНИЕ СЛАУ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ

1.1 Описание метода постой итерации

Системы алгебраических уравнений (СЛАУ) имеют вид:

или, при записи в матричной форме:

A? x = b ,

В практике используют два типа методов численного решения СЛАУ - прямые и косвенные. При использовании прямых методов СЛАУ приводится к одной из специальных форм (диагональной, треугольной) позволяющих точно получить искомое решение (если таковое существует). Наиболее распространенным прямым методом решения СЛАУ является метод Гаусса. Итерационные методы служат для поиска приближенного решения СЛАУ с заданной точностью. Следует отметить, что итерационный процесс не всегда сходится к решению системы, а только тогда, когда последовательность получаемых при расчетах приближений стремиться к точному решению. При решении СЛАУ методом простой итерации ее преобразуют к виду, когда в левой части находится только одна из искомых переменных:

Задав некоторые исходные приближения xi, i=1,2,…,n, подставляют их в правую часть выражений и вычисляют новые значения x. Процесс повторяют до тех пор, пока максимальная из невязок, определяемых по выражению:

не станет меньше заданной точности е. Если максимальная невязка при k-ой итерации окажется больше максимальной невязки при k-1-ой итерации, то процесс аварийно завершают, т.к. итерационный процесс расходится. Для минимизации количества итераций новые значения x можно вычислять с использованием значением невязок на предыдущей итерации:

Невязки, в этом случае определяют по выражению:

1.2 Исходные данные

В качестве исходных данных дана следующая СЛАУ:



2. УТОЧНЕНИЕ КОРНЯ МЕТОДОМ КАСАТЕЛЬНЫХ

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

Уравнение типа F(x)=0 или x=f(x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;...? корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале [a,b]. При этом на интервале должен существовать только один корень. Решение уравнения складывается из двух этапов:

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

2. уточнения корня, т.е. доведения его численного значения до заданной степени точности.

Для отделения корня (определения начального приближения) следует пользоваться графическим методом. Уточнение корня может быть произведено одним из следующих методов.

При решении нелинейного уравнения методом хорд задаются интервал [a,b], на котором существует только одно решение, и точность е. Затем через две точки с координатами (a,F(a)) и (b,F(b)) проводим отрезок прямой линии (хорду) и определяем точку пересечения этой линии с осью абсцисс (точка c). Если при этом F(a)·F(c)<0, то правую границу интервала переносим в точку с (b=c). Если указанное условие не выполняется, то в точку c переносится левая граница интервала (а=с). Поиск решения прекращается при достижении заданной точности |F(c)|< е. Для определения точки пересечения хорды с осью абсцисс воспользуемся следующей формулой



2.2 Программа уточнения корня

REM Ocadchenko

CLS

INPUT "e="; e

m: INPUT "x0="; x

F = 2 * EXP(-x)

F2 = 2 * EXP(-x)

IF F * F2 > 0 THEN

DO

F = 2 * EXP(-x)

F1 = -2 * EXP(-x)

x = x - F / F1

LOOP WHILE ABS(F) > e

PRINT "x="; x

ELSE

PRINT "Process rashoditsy"

GOTO m

END IF

END

2.3 Экран вывода

e=? 0.01

x0=? 2.5

x=? 6.5

3. численное интегрирование по правилу прямоугольника

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

Определенным интегралом функции f(x), взятом в интервале от a до b, называется предел, к которому стремится интегральная сумма при стремлении всех промежутков Дxi к нулю

При приближенном вычислении определенного интеграла шаг интегрирования h=Дx выбирается конечным:

где Ii - элемент интегральной суммы. Заменяя подынтегральную функцию на каждом шаге отрезками линий нулевого, первого и второго порядков, получаем приближенные формулы для вычисления интеграла методами прямоугольников, трапеций и Симпсона соответственно.



Заменяем график функции F(x) горизонтальной линией (линии нулевого порядка) и вычисляем значение элемента интегральной суммы как площадь прямоугольника

где h - шаг интегрирования, у0 - значение функции в точке х=х0 у(х0)=у0



4. WinRAR

4.1 Общие сведения о программе

4.1.1 Назначение и отличительные особенности

WinRAR- это архиватор файлов в формат RAR и ZIP для 32-битных и 64-разрядных операционных систем Windows и Pocket PC с высокой степенью сжатия. Является одним из лучших архиваторов по соотношению степени сжатия к скорости работы. Существует несколько версий RAR для разных операционных систем, в частности, RAR для Windows, Linux, DOS, OS/2, UNIX.

RAR для Windows поставляется в двух вариантах:

· версия с графическим интерфейсом пользователя- WinRAR.exe;

· консольная версия - Rar.exe, запускаемая из командной строки и работающая в текстовом режиме. Консольную версию RAR удобно использовать для вызова из пакетных файлов, для запуска из приглашения DOS и др.

Некоторые отличительные особенности WinRAR следующие:

· полная поддержка архивов RAR и ZIP;

· использование оригинального высокоэффективного алгоритма сжатия данных;

· наличие графической оболочки с поддержкой технологии перетаскивания;

· возможность использования интерфейса командной строки;

· управление архивами других форматов (CAB, ARJ, LZH, TAR, GZ, ACE, UUE, BZ2, JAR, ISO);

· поддержка метода непрерывного архивирования, при котором может быть достигнута на 10-50% более высокая степень сжатия, чем дают обычные методы, особенно если упаковывается значительное количество небольших файлов однотипного содержания;

· поддержка многотомных архивов;

· возможность восстановления физически поврежденных архивов;

· наличие других дополнительных функций, например, шифрования данных и имён файлов в архиве, добавления архивных комментариев, ведения протокола ошибок и пр.

4.1.2 Ограничения WinRAR

Количество файлов, которое можно добавить в архив, зависит от объёма доступной памяти и длины имён файлов. Для добавления одного файла в архив RAR требуется ориентировочно 128 байт памяти. Например, для архивации миллиона файлов необходимо около 128 Мбайт памяти. WinRAR тестировался в работе с более чем 10 миллионами файлов. Максимальный размер архива RAR, равно как и любого файла в архиве RAR, практически не ограничен - он составляет 8 экзабайт (что равнозначно 8 589 934 591 Гбайт или 9 223 372 036 854 775 807 байт).

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

4.1.3 Системные требования WinRAR

· Процессор: Intel Pentium (или совместимый)

· Операционная система: Windows 95, 98, Me, NT 4.0, 2000, 2003, XP, Vista, Win7

· Оперативная память: 64MB

· Свободное место на диске: 3MB

4.2 Интерфейс WinRAR

WinRAR совместим с Windows7, как с 32-разрядными, так и с 64-разрядными системами. Программа доступна более чем 50 языках, а также во всех действующих операционных системах. WinRAR - единственное программное обеспечение сжатия файлов, которое полностью принято во всех странах.

Меню WinRAR содержит следующие пункты: «Файл», «Команды», «Операции», «Избранное», «Параметры» и «?» (Справка).

Рис.4.1ИнтерфейсWinRAR

программа корень меню файл

Ещё один элемент интерфейса - панель инструментов. Она находится ниже меню и выше списка файлов. Кнопки на панели инструментов повторяют пункты из меню «Команды» (у всех пунктов в этом меню есть «горячие клавиши» для быстрого доступа). Во время просмотра содержимого архива некоторые кнопки могут быть отключены, если их функции неприменимы к архиву. Можно выбрать отображаемые кнопки, убрать текст с кнопок или уменьшить их размер в диалоге «Общие параметры» или щелкнув правой кнопкой мыши на панели инструментов.

Под панелью инструментов находится маленькая кнопка со стрелкой вверх и строка списка дисков. При нажатии кнопки «Вверх» происходит переход в родительскую папку. Список дисков служит для выбора текущего диска. Этот список также можно открыть нажатием клавиши <F4>. При желании кнопку «Вверх» и список дисков можно перетащить в правый угол панели инструментов.

Ниже панели инструментов расположено файловое окно. В нём отображается содержимое текущей папки или, если в WinRAR открыт архив, содержимое архива. Эти режимы называются режимом управления файлами и режимом управления архивами. Для каждого файла выводится следующая информация: имя, размер, тип и дата изменения. Для файлов в архиве показываются ещё два параметра - упакованный размер и значение CRC32. CRC32 - это особая контрольная сумма, вычисляемая на основании данных файла, с помощью неё можно сразу определить, одинаковы ли упакованные в архиве файлы, не прибегая к их распаковке. Файлы с одинаковым содержимым всегда имеют одинаковые CRC32. Все параметры представлены в виде колонок. Порядок сортировки файлов можно поменять щелчком на заголовке колонки (там же синей стрелкой указывается направление сортировки). Кроме того, можно изменить ширину колонок, перетаскивая мышью разделители заголовков колонок. Несколько дополнительных параметров списка можно изменить в диалоге «Список файлов».

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

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

Внизу окна WinRAR (под списком файлов) находится строка состояния. В её левой части расположены два маленьких значка: «диск» и «ключ». Щелчком по значку «диск» можно изменить текущий диск, а щелчком по «ключу» - текущий пароль. Две соответствующие команды также есть в меню «Файл». По умолчанию значок «ключ» жёлтого цвета, но если введён пароль, то он становится красным. В средней части строки состояния выводится информация об общем размере выделенных файлов или о текущем состоянии. В правой части строки состояния отображаются общее количество файлов в текущей папке и их размер.

4.3 Режимы управления файлами и архивами

Оболочка WinRAR имеет два основных режима: режим управления файлами и режим управления архивами.

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

В режиме управления архивами в окне WinRAR отображается список файлов и папок в открытом архиве. Здесь также можно выделить файлы и папки и выполнить с ними различные действия, специфичные для архива, например, распаковать, протестировать или добавить комментарий.

В обоих режимах можно изменить текущую папку (на диске или в архиве). Для перехода в родительскую папку необходимо нажать клавишу <BackSpace> (BS) или <Ctrl+PgUp>, либо дважды щелкнуть мышью на папке «..» в списке файлов. Если сделать это в корневой папке архива, то закроется архив и осуществится переход в ту папку на диске, в которой он находится. Для перехода в другую папку необходимо нажать <Enter>, <Ctrl+PgDn> или дважды щелкнуть мышью на этой папке. Аналогичное действие на файле архива приведет к открытию архива. Для перехода в корневую папку диска служит комбинация клавиш <Ctrl+\>.

Для входа в режим управления файлами запускается WinRAR двойным щелчком на его значке или вводится в командной строке «WinRAR» без параметров.

Для входа в режим управления архивами запускается WinRAR в режиме управления файлами, помещается курсор на выбранный архив и нажимается <Enter> (это же действие выполняется при выборе пункта «Открыть архив» в меню «Файл» или при двойном щелчке мышью на имени архива). Кроме того, вход в режим управления архивами происходит при нажатии на архиве <Enter> или двойном щелчке мышью в оболочке Windows (в Проводнике или на Рабочем столе), но только в том случае, если WinRAR ассоциирован с архивами (что делается по умолчанию во время установки). Связать WinRAR с архивами несложно и после установки - для этого служит диалог «Параметры интеграции». И, наконец, зайти в нужный архив также можно непосредственно из командной строки, передав WinRAR в командной строке в виде единственного параметра имя этого архива.

4.4 Использование контекстных меню

Если при установке WinRAR не включена опция «Встроить WinRAR в оболочку», то в обычные контекстные меню папок и файлов, вызываемые щелчком на них правой кнопкой мыши в Проводнике или на Рабочем столе, будут добавлены несколько дополнительных пунктов.

Для архивов WinRAR добавляются элементы «Извлечь файлы...», «Извлечь в <имя папки>» и «Извлечь в текущую папку». Все эти команды вызывают WinRAR для извлечения содержимого архива, но первая команда позволяет ввести имя папки для распаковки и некоторые параметры извлечения в диалоге указания пути и параметров извлечения, вторая извлекает файлы из архива в предложенную папку, а третья - в текущую папку без дополнительных запросов. При распаковке группы архивов контекстное меню также содержит пункт «Извлечь каждый архив в отдельную папку», позволяющий поместить распакованное содержимое каждого архива в отдельную папку.

Рис. 4.2 Извлечение из архива

WinRAR также изменяет в контекстном меню архивов пункт «Свойства», дополняя его вкладкой для отображения информации об архиве и комментария архива, если он есть. Информация об архиве аналогична той, которая выводится командой «Информация» с той лишь разницей, что в этом диалоге отображается только факт наличия электронной подписи, но нет подробных сведений о ней.

В контекстные меню обычных файлов и папок WinRAR помещает пункты «Добавить в архив...», «Добавить в архив <имя архива>», «Добавить в архив и отправить по e-mail» и «Добавить в архив <имя архива> и отправить по e-mail», где <имя архива> заменяется действительным именем архива.



Рис. 4.3 Добавление в архив

Обе команды «Добавить…» вызывают WinRAR для добавления выбранных файлов в архив, но первая команда позволяет ввести имя архива и некоторые параметры архивации в диалоге ввода имени архива и его параметров, а вторая немедленно начинает добавлять файлы в предложенный архив без дополнительных запросов. Аналогично, обе команды «…e-mail» предназначены для упаковки выбранных файлов и прикрепления созданного архива к сообщению электронной почты, но первая команда позволяет указать дополнительные параметры, а вторая сразу начинает выполнять операцию без всяких запросов. Команды «…e-mail» работают только в том случае, если установленная почтовая программы совместима с интерфейсом MAPI (этот интерфейс поддерживают большинство современных почтовых программ).



ЗАКЛЮЧЕНИЕ

В результате выполнения курсовой работы:

- были получены навыки программирования на языке Q-Basic:

- создание собственных процедур и функций;

- применение циклов;

- использование библиотечных процедур;

- освоена работа в среде программирования Q-Basic;

- изучены численные методы решения СЛАУ;

- изучены численные методы решения нелинейных уравнений;

- изучены методы численного интегрирования.



СПИСОК ЛИТЕРАТУРЫ

1. В. А. Аллилуев, Е. Д. Березкин, А. В. Тютин «Основы программирования на языке QBasic»:Учебное пособие. ЮРГТУ, 2010

2. Гринчишин Я. Т. и др. «Алгоритмы и программы на бейсике»: Учебное пособие для студентов педагогических вузов по физико-математическим специальностям. Просвещение, 2008.-160 стр.

Размещено на Allbest.ru