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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

REM Ocadchenko

CLS"e="; e: INPUT "x0="; x= 2 * EXP(-x)= 2 * EXP(-x)F * F2 > 0 THEN= 2 * EXP(-x)= -2 * EXP(-x)= x - F / F1WHILE ABS(F) > e"x="; x"Process rashoditsy"mIF

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

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

.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;

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

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

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

·              поддержка метода непрерывного архивирования, при котором может быть достигнута на 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

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

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

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

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

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

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

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

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