Численные методы решения уравнений информатика

Информатика, часть 1. «Численные методы»

Государственный комитет РФ по связи и

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

телекоммуникаций и информатики

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

Кафедра прикладной математики и кибернетики.

Для специальностей 2305, 2306, 2307.

Список литературы – 9 наименований.

Утверждено редакционно-издательским советом СибГУТИ в качестве методических указаний.

телекоммуникаций и информатики, 1999 г.

1. Введение

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

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

Все многообразие численных методов подразделяют на две группы — точные и приближенные.

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

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

Численные методы реализуются конечными или бесконечными вычислительными алгоритмами.

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

Настоящие методические указания содержат основы курса «Численные методы». Для более детального изучения данного курса следует воспользоваться рекомендуемой литературой. Кроме того, для выполнения курсовой работы необходимо использовать знания, полученные в предыдущем семестре в процессе изучения курса «Вычислительная техника и программирование».

2. Абсолютная и относительная погрешность

Определения

Определение. Абсолютной погрешностью величины x называется величина

где x – приближенное значение, x0 – точное значение.

Следствие этой формулы:

Пример. Результат измерений длины комнаты – 10,2 ± 0,01 м.

Здесь, 10,2 м – приблизительное значение – результат измерений, 0,01 – погрешность измерений – абсолютная погрешность.

Обычно должно быть D x ú -1 ï + ú 2 ï; ï -5 ï > ú -2 ï + ú 1 ï; ï 4 ï > 1 + ú -2 ï.

После этого приводим систему к виду, удобному для итераций.

Получаем: , находим

Аналогично находятся последующие приближения X(3), X(4) и т. д.

Сравнив и , можно заметить, что они отличаются друг от друга очень незначительно (в третьем знаке после запятой) и, следовательно, в качестве решения с точностью e =10-2 можно взять X(10) . Для сведения: точное решение этой СЛУ – .

4. Решение нелинейных уравнений

Если непрерывная функция f(x) принимает значения различных знаков на концах отрезка [a, b], то есть f(a)×f(b)

Численные методы решения алгебраических и трансцендентных уравнений в среде Microsoft Excel

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

Задачи урока:

Образовательные – совершенствование умений студентов при решении алгебраических и трансцендентных уравнений в среде электронных таблиц MS Excel. Выработать умение применять теоретические знания в практических расчетах;
Развивающие – познакомить студентов с применением компьютеров в качестве помощников при решении уравнений. Развивать у студентов математическую речь: создать ситуацию для применения основных понятий в речи; абстрактное мышление: создать ситуацию предъявления материала от общего к частному и от частного к общему, стимулировать самостоятельное обобщение материала сильными студентами;творческого мышления через создание условий для самореализации творческого потенциала обучающихся;
Воспитательные – выработать у студентов умение рационально использовать время и возможности компьютерных технологий при решении задач. Воспитывать интерес к предмету через ситуацию успеха и взаимодоверия;ответственность перед самим собой.

Тип урока: комбинированный урок.

Вид урока: практическое занятие, продолжительность – 2 часа.

Оборудование урока:

Компьютеры с OS MS Windows;
Программа Microsoft Excel;
Презентация по теме, выполненная в программе PowerPoint;
Карточки с заданиями для самостоятельной работы.

Структура урока:

1.1. Мобилизующее начало, постановка целей и задач на урок;

1.2.Фронтальный опрос с целью выявления основных этапов решения задач с использованием ЭВМ;

1.3. Постановка задачи с целью повторения алгоритма решения уравнения f(x)=0 на отрезке [а;в] различными методами;

1.4.Подведение итогов 1 этапа урока.

2.Применение знаний, формирование умений и навыков:

2.1.Беседа с целью формулировки задания для самостоятельной работы и инструктажа по ее организации;

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

2.3.Подведение итога урока.

В данном уроке особое внимание уделено визуальному представлению информации – в ходе урока с помощью проектора демонстрируются слайды, подготовленные в пакете презентационной графики Microsoft PowerPoint.

ХОД УРОКА

1. Актуализация знаний

Мобилизующее начало, постановка целей и задач на урок.

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

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

В общем случае процесс решения задачи с использованием ЭВМ состоит из следующих этапов:

1.Постановка задачи и построение математической модели (этап моделирования);
2.Выбор метода и разработка алгоритма (этап алгоритмизации);
3.Запись алгоритма на языке, понятном ЭВМ (этап программирования);
4.Отладка и использования программы на ЭВМ (этап реализации);
5.Анализ полученных результатов (этап интерпретации).

— В чем заключается постановка задачи?

— Постановка задачи: Пусть дано уравнение f(x) = 0, (a, b) — интервал, на котором f(x) имеет единственный корень. Нужно приближенно вычислить этот корень с заданной точностью.

— В чем заключается общая постановка задачи?

— Общая постановка задачи. Найти действительные корни уравнения f(x) =0, где f(x) – алгебраическая или трансцендентная функция.

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

— В чем заключается задача численного нахождения корней уравнения?

— Задача численного нахождения корней уравнения состоит из двух этапов:

1. Отделение (локализация) корня;

2. Приближенное вычисление корня до заданной точности(уточнение корней)

— Какая задача называется уточнения корня?

-Уточнение корня. Если искомый корень уравнения f(x)=0, отделен, т.е. определен отрезок [a,b], на котором существует только один действительный корень уравнения, то далее необходимо найти приближенное значение коня с заданной точностью.

— Какими методами можно производить уточнения корня?

— Уточнения корня можно производить различными методами:

1) Метод половинного деления (бисекции);

2) Метод итераций;

3) Метод хорд (секущих);

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

5) Комбинированные методы.

— Объясните алгоритм решения уравнения f(x)=0 на отрезке [а;в] различными методами.

Применение знаний, формирование умений и навыков:

Практическое задание «Решение алгебраических и трансцендентных уравнений в среде Microsoft Excel»

Ознакомиться с теоретической частью задания;
Провести расчет для своего варианта индивидуального задания в Microsoft Excel
Оформить презентацию в Ms PowerPoint, включающую:
постановку задачи;
алгоритм расчета;
таблицу с расчетом из Ms Excel, график исходной функции;
результат расчета и его анализ.

Индивидуальное расчетное задание

Дано: x 3 + 8x + 10 = 0

Найти: Отделить корень заданного уравнения, пользуясь графическим методом, и по методам вычислите один корень с точностью 0,001 при помощи программы на ПК

Графический метод: Для отделения корней уравнения естественно применять графический метод. График функции у = f (х) с учетом свойств функции дает много информации для определения числа корней уравнения f (х) = 0.

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

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

если функция f(x) на концах отрезка [а,b] значения разных принимает значения разных знаков то делим отрезок на 10 равных частей и находим ту часть, которая содержит корень (таким способом мы можем уменьшить длину отрезка, содержащего корень, в 10 раз);
повторим действия предыдущего пункта для полученного отрезка.

Этот процесс можно продолжать до тех пор, пока длина отрезка не станет меньше заданной погрешности.

Задания для студентов первой группы

Найдите приближенное значение уравнения заданного функцией x 3 + 8x + 10 = 0, с точностью е=0,001
Представьте графически поставленную задачу в среде Microsoft Excel;

Метод половинного деления:Постановка задачи: Пусть дано уравнение f(x) = 0, (a, b) — интервал, на котором f(x) имеет единственный корень. Нужно приближенно вычислить этот корень с заданной точностью.

Примечание: Заметим, что если f(x) имеет k корней, то нужно выделить соответственно k интервалов.

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

Алгоритм для программной реализации:

а:=левая граница b:= правая граница
m:= (a+b)/2 середина
определяем f(a) и f(m)
если f(a)*f(m) e повторяем, начиная с пункта 2
m — искомый корень.

Задания для студентов второй группы

Найдите приближенное значение уравнения заданного функцией x 3 + 8x + 10 = 0, с точностью е=0,001.
Расчет уравнения по методу половинного деления в среде Microsoft Excel.

Метод простой итерации: Смысл метода простой итерации состоит в том, что мы представляем уравнение f(x) в виде ) и по формуле будем строить итерации, которые сходятся к искомому корню с интересующей степенью точности, но тут есть проблемы: возможно f(x) очень сложно представить в таком виде, да и не факт, что любая будет строить сходящиеся итерации, поэтому алгорим сводится к тому, чтобы оптимально найти .

Подготовка:

1. Ищем числа m и M такие, что на (a, b);

2. Представляем , где ;

Алгоритм:

1. Выбираем х₀ из (a, b);

2. Вычисляем ;
3. Проверяем условие , где q=(M-m)/(M+m);

4. Если оно ложно, то переходим к пункту 7;

6. Переходим к пункту 2;

7. х₁ – искомый корень.

Задания для студентов третьей группы

Найдите приближенное значение уравнения заданного функцией x 3 + 8x + 10 = 0, с точностью е=0,001
Расчет уравнения по методу простой итерации в среде Microsoft Excel.

Метод хорд: Метод хорд заключается в замене кривой у = f(x) отрезком прямой, проходящей через точки (а, f(a)) и (b, f(b)). Абсцисса точки пересечения прямой с осью ОХ принимается за очередное приближение.

Чтобы получить расчетную формулу метода хорд, запишем уравнение прямой, проходящей через точки (a, f(a)) и (b, f(b)) и, приравнивая у к нулю, найдем х:

Алгоритм метода хорд:

2) Вычислим следующий номер итерации: k = k + 1.

Найдем очередное k-e приближение по формуле: x_k = a — f(a)(b — a)/(f(b) — f(a)). Вычислим f(xk);

3) Если f(x_k)= 0 (корень найден), то переходим к п. 5.

4) Если |x_k – x_k–1| > ε, то переходим к п. 2;

5) Выводим значение корня x_k;

Задания для студентов четвертой группы

Найдите приближенное значение уравнения заданного функцией x 3 + 8x + 10 = 0, с точностью е=0,001.
Расчет уравнения по методу хорд в среде Microsoft Excel.
Метод касательных: В точке пересечения касательной с осью Оx переменная у = 0. Приравнивая у к нулю, выразим х и получим формулу метода касательных:

Теорема. Пусть на отрезке [а, b]выполняются условия:

1) функция f(x)и ее производные f'(х)и f»(x) непрерывны;

2) производные f'(x) и f»(x)отличны от нуля и сохраняют определенные постоянные знаки;

3) f(a)× f(b) 0, то итерационная последовательность сходится монотонно

Задания для студентов пятой группы

Найдите приближенное значение уравнения заданного функцией x 3 + 8x + 10 = 0, с точностью е=0,001.
Расчет уравнения по методу касательных в среде Microsoft Excel.

Студенты выполняют задания в группах и показывают полученное решение у доски (один представитель от группы), делают выводы о проделанной работе.

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

Уточнения корня производилось различными методами:

1) методом бисекции;

2) методом итераций;

3) методом секущих;

4) методом Ньютона;

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

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

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

4. У метода хорд и у метода Ньютона имеется общий недостаток: на каждом шаге проверяется точность значения.

Численные методы решения систем нелинейных уравнений

Введение

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

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

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

(1)

Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

(2)

Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].

Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

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

Так, в публикации [2], на основании проведенных вычислительных экспериментов, доказано, что библиотечная функция newton_krylov, предназначенная для решения больших систем нелинейных уравнений, имеет в два раза меньшее быстродействие, чем алгоритм TSLS+WD
(two-step least squares), реализованный средствами библиотеки NumPy.

Целью настоящей публикации является сравнение по числу итераций, быстродействию, а главное, по результату решения модельной задачи в виде системы из ста нелинейных алгебраических уравнений при помощи библиотечной функции scipy.optimize.root и методом Ньютона, реализованного средствами библиотеки NumPy.

Возможности решателя scipy.optimize.root для численного решения систем алгебраических нелинейных уравнений

Библиотечная функция scipy.optimize.root выбрана в качестве базы сравнения, потому что имеет обширную библиотеку методов, пригодных для сравнительного анализа.

scipy.optimize.root(fun, x0, args=(), method=’hybr’, jac=None, tol=None,callback=None, ptions=None)
fun — Векторная функция для поиска корня.
x0 –Начальные условия поиска корней

method:
hybr -используется модификация Пауэлл гибридный метод;
lm – решает системы нелинейных уравнений методом наименьших квадратов.
Как следует из документации [3] методы broyden1, broyden2, anderson, linearmixing, diagbroyden, excitingmixing, krylov являются точными методами Ньютона. Остальные параметры являются «не обязательными» и с ними можно ознакомится в документации.

Методы решения систем нелинейных уравнений

Приведенный далее материал действительно можно прочитать в литературе, например в [4], но я уважаю своего читателя и для его удобства приведу вывод метода по возможности в сокращенном виде. Те, кто не любит формулы, этот раздел пропускают.

В методе Ньютона новое приближение для решения системы уравнений (2) определяется из решения системы линейных уравнений:

(3)

Определим матрицу Якоби:

(4)

Запишем(3) в виде:

(5)

Многие одношаговые методы для приближенного решения (2) по аналогии с двухслойными итерационными методами для решения систем линейных алгебраических уравнений можно записать в виде:

(6)

где — итерационные параметры, a — квадратная матрица n х n, имеющая обратную.

При использовании записи (6) метод Ньютона (5) соответствует выбору:

Система линейных уравнений (5) для нахождения нового приближения может решаться итерационно. В этом случае мы имеем двухступенчатый итерационный процесс с внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основе итерационного метода Зейделя

При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений. Нелинейный метод Зейделя применительно к решению (2) дает:

(7)

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

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

(8)

Выбор модельной функции

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

Функция f создаёт систему из n нелинейных уравнений, решение которой не зависит от числа уравнений и для каждой из n переменных равно единице.

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

Только один из методов, приведенных в документации [3] прошёл тестирование по результату решения модельной функции, это метод ‘krylov’.

Решение для n=100:

Вывод: С увеличением числа уравнений вдвое заметно появление ошибок в решении. При дальнейшем увеличении n решение становится не приемлемым, что возможно из-за автоматической адаптации к шагу, эта же причина резкого падения быстродействия. Но это только моё предположение.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью программы написанной на Python 3 с учётом соотношений (1)-(8) для отыскания корней по модифицированному методу Ньютона

Решение для n=100:

Решение для n=200:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1.]
Newton iteration = 14
Newton method time 1.869 seconds

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

Получим:
Solution:
[ 0.96472166 0.87777036 0.48175823 -0.26190496 -0.63693762 0.49232062
-1.31649896 0.6865098 0.89609091 0.98509235]
Newton iteration = 16
Newton method time 0.046 seconds

Вывод: Программа работает и при изменении модельной функции.

Теперь вернёмся к начальной модельной функции и проверим более широкий диапазон для n, например в 2 и 500.
n=2
Solution:
[1. 1.]
Newton iteration = 6
Newton method time 0.048 seconds
n=500

источники:

http://urok.1sept.ru/articles/674330

http://habr.com/ru/post/419453/