Вычисления корней нелинейного уравнения с заданной точностью

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ П.О. СУХОГО Машиностроительный факультет Кафедра «Информационные технологии»

Пояснительная записка

к курсовой работе по дисциплине «Информатика»

на тему: «Вычисления корней нелинейного уравнения с заданной точностью»

Гомель 2013

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

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

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

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

О стремительном темпе развития информационных технологий мы с вами читаем и слышим почти каждый день. Эти темпы действительно впечатляют. Однако в компьютерном мире остается одна самая важная область, изменения в которой происходят крайне медленно. Программирование, кодирование, составление исходных текстов — ключевой элемент в создании любого приложения сегодня происходит так же, как и сорок лет назад. Разработчик применяет крайне ограниченный набор логических конструкций (условный оператор и операторы присваивания и цикла) и небольшое число стандартных типов данных. Причем такой подход ничуть не изменился, хотя сменилось уже не одно поколение языков программирования. Например, на смену Си и Паскалю пришла Java и Mathcad.

Одной из основных областей применения ПК являются математические и научно-технические расчеты. Сложные вычислительные задачи, возникающие при моделировании технических устройств и процессов, можно разбить на ряд элементарных: вычисление интегралов, решение уравнений, решение дифференциальных уравнений и т. д. Для таких задач уже разработаны методы решения, созданы математические системы. Наиболее подходящей для этой цели является одна из самых мощных и эффективных математических систем — Mathcad, которая занимает особое место среди множества таких систем (Matlab, Maple, Mathematica и др.).

1. Теоретические сведения к работе

Mathcad — это мощная и в то же время простая универсальная среда для решения задач в различных отраслях науки и техники, финансов и экономики, физики и астрономии, математики и статистики. Mathcad остается единственной системой, в которой описание решения математических задач задается с помощью привычных математических формул и знаков. Mathcad позволяет выполнять как численные, так и аналитические (символьные) вычисления, имеет чрезвычайно удобный математико-ориентированный интерфейс и прекрасные средства научной графики.

Язык программирования Mathcad по своей структуре очень похож на язык FRED интегрированного пакета Framework. Линии программ Mathcad более наглядны (особенно для обучения структурному программированию), чем операторные скобки традиционных языков — begin-end на языке Pascal, фигурные скобки на языке С, оператор list на языке FRED и т. д.

Кроме возможности программировать следует отметить следующие основные возможности Mathcad:

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

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

1.1 Отделение действительных корней нелинейного уравнения

Численное решение нелинейных (алгебраических или трансцендентных) уравнений вида

заключается в нахождении значений x, удовлетворяющих (с заданной точностью) данному уравнению и состоит из следующих основных этапов:

Отделение (изоляция, локализация) корней уравнения.

Уточнение с помощью некоторого вычислительного алгоритма конкретного выделенного корня с заданной точностью.

Отметим, что первая задача существенно сложнее второй, так как не существует достаточно эффективного метода ее решения в общем случае.

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

Отделить корни уравнения (1) можно графически и аналитически.

Графический метод основан на построении графика функции y=f (x). Если построить график данной функции, то искомым отрезком [,], содержащим корень уравнения, будет отрезок оси абсцисс, содержащий точку пересечения графика с этой осью. Иногда выгоднее функцию f (x) представить в виде разности двух более простых функций, т. е. и строить графики функций и. Абсцисса точки пересечения этих графиков и будет являться корнем уравнения, а отрезок на оси абсцисс которому принадлежит данный корень, будет являться интервалом изоляции.

При аналитическом способе отделения корней полезной оказывается теорема.

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

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

Пусть — алгебраический многочлен и уравнение (1) не имеет кратных корней. Составим систему Штурма для многочлена :

, ,…, ,

где , — взятый с обратным знаком остаток от деления многочлена на , — взятый с обратным знаком остаток при делении многочлена на и т. д. Последним элементом системы Штурма является отличное от нуля действительное число.

Теорема 2 (Штурма). Число действительных корней уравнения (1) на отрезке равно разности между числом перемен знаков в последовательности Штурма при и .

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

. (2)

Теорема 3. Если полное метрическое пространство и осуществляет сжатие в себя, то существует одна и только одна неподвижная точка отображения такая, что

. (3)

При этом решением уравнения (3) является предел последовательности

(4)

при любом. Если — неподвижная точка, то для сходимости процесса (4) справедлива оценка

. (5)

1.2 Методы уточнения действительных корней нелинейного уравнения

Методы отделения корней весьма удобны и просты. Однако они дают ответ только на вопрос локализации корня, и позволяю найти грубое приближение этого корня. Если же требуется найти более точное значение корня, то следует воспользоваться итерационными методами.

Суть любого итерационного метода решения уравнения, заключается в следующем. Пусть известен малый промежуток [, ], в котором содержится единственный корень x= уравнения (1). Из достаточно малой окрестности корня выбирается произвольная точка х0 — начальное приближение к корню уравнения и строится последовательность точек — посредством рекуррентного соотношения:, k=1, 2, …. При этом последовательность — должна сходиться к корню x=, что обеспечивается соответствующим выбором .

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

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

1.2.1 Метод хорд

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

. (13)

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

Геометрическая интерпретация метода хорд:

Рисунок 1 — Геометрическая интерпретация метода хорд Описанный метод называется также методом секущих или методом линейной интерполяции. Последовательные приближения в методе хорд образуют монотонную ограниченную сверху или снизу корнем последовательность. При этом справедлива оценка

(14)

где, .

Метод секущих можно рассматривать как метод итерации для эквивалентного уравнения

где и начальное приближение берется так, что .

1.2.2 Метод касательных (Ньютона)

Если в уравнении (6) положить

то получим метод Ньютона (касательных)

. (15)

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

и. Следовательно, существует такая окрестность корня, в любой точке которой справедливо неравенство. Начальное приближение в (15) целесообразно выбирать так, чтобы выполнялось условие .

Для скорости сходимости метода справедливы оценки

(16)

(17)

где,. Эти оценки указывают на квадратичную сходимость метода Ньютона.

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

Последовательные приближения сходятся к действительному корню уравнения монотонно со стороны .

Рисунок 2 — Геометрическая интерпретация метода касательных

1.2.3 Метод половинного деления

Предположим, что корень отделён на отрезке [a, b] и знаки f (a) и f (b) различны (функция меняет знак при переходе через корень).

Положим a0=a и b0=b и вычислим значения функции в левом конце отрезка, f (a0), и в его середине:

Сравним знаки чисел f (a0), и f (c0). Если эти знаки различны, то корень x лежит в интервале (a0, c0); если же одинаковы, то тогда различны знаки f (c0) и f (b0), и корень лежит в интервале (c0, b0). (Возможен ещё случай f (c0)=0; тогда корень уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке [a, c0] либо [c0, b], длина которого ровно в два раза меньше длины исходного отрезка. Обозначим этот отрезок половинной длины через [a1, b1] (то есть положим a1 =a0, b1 =c0 в случае, когда f (a0) и f (c0) разных знаков, и a1 =c0, b1=b0 в случае, когда одного знака).

Далее повторим процесс для отрезка [a1, b1]: снова отыщем его середину c1, найдём значение функции f (c1) и сравним знак этого числа со знаком f (a1); если знаки разные, то корень отделён на [a1, c1]= [a2, b2], если одинаковые, то на [c1, b1]= [a2, b2], (или же оказывается, что f (c1)=0; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рисунок 3 — Геометрическая интерпретация метода половинного деления Поступая тем же образом и далее, получаем, что после k делений длина отрезка, на котором лежит корень, сокращается в 2k раз и становится равной

(если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с ci при некотором i). Пусть е заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство. Очевидно, что если при этом положить

то расстояние от корня, лежащего где-то в интервале (ak; bk), до середины этого интервала x будет не больше е, то есть приближённое равенство x= будет выполнено с нужной точностью.

1.3 Алгоритмы методов уточнения действительных корней нелинейного уравнения

Алгоритм метода деления отрезка пополам Рисунок 4 — Блок-схема метода половинного деления Алгоритм метода касательных Рисунок 5 — Блок-схема метода касательных (Ньютона) Алгоритм метода хорд секущих Рисунок 6 — Блок-схема метода хорд

2. Алгоритмический анализ задачи

2.1 Полная постановка задачи

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

Метод решения: касательных, половинного деления и хорд.

2.2 Графическая схема алгоритма и ее описание

Рисунок 7 — Алгоритм решения задачи На данной блок-схеме кратко представлены основные этапы решения задачи в системе Mathcad. Этапы решения в системе Mathcad более подробно представлены в пункте 3.1.

3. Описание расчетов в среде Mathcad

3.1 Описание реализации базовой модели в MathCAD

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

Первая производная Вторая производная График Строим график функции на промежутке с корнем.

С помощью функции root находим корень.

Создаём блок программирования, который осуществит решение методом касательных.

Посчитаем корни методом касательных с различной точностью.

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

Создаём блок программирования, который осуществит решение методом половинного деления.

Посчитаем корни с различной точностью.

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

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

Посчитаем корни методом хорд с различной точностью.

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

Создаём график сравнения числа итераций в зависимости от точности

нелинейный уравнение мathcad итерация На основании графика делаем вывод о качестве методов решения.

3.2 Выводы о проделанной работе, анализ полученных результатов

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

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

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

Заключение

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

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

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

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

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

Список использованных источников

1. Турчак Л. И. Основы численных методов. — М.: Наука, 1987.

2. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Н. Численные методы. — М.: Наука, 1987.

3. Трохова Т. А. Практическое пособие по теме «Основные приемы работы в системе MathCad, версии 6.0.» для студентов всех специальностей дневного и заочного отделений. — Гомель: ГГТУ, 1998.

4. Грудецкий Г. А., Мурашко И. А. Практическое пособие по теме «Графические средства пакета MathCad» для студентов всех специальностей дневного и заочного отделений. — Гомель: ГГТУ, 2001.

5. Токочаков В. И. Практическое пособие по теме «Решение систем алгебраических и дифференциальных уравнений в среде MathCad Windows» для студентов всех специальностей дневного и заочного отделений. — Гомель: ГГТУ, 2000.

6. И. Н. Мастяева О.Н. Семенихина.- Численные методы: Учебное пособие / Московский международный институт эконометрики, информатики, финансов и права. — М., 2003. — 102 с.