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

1 2 3 4 5 6 7

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

ИННОВАЦИОННЫЙ ЕВРАЗИЙСКИЙ УНИВЕРСИТЕТ

Учебно-методический комплекс дисциплины

Методические указания

К ЛАБОРАТОРНЫМ работам

по дисциплине: Численные методы

ПАВЛОДАР, 2019

Составитель:

ст. преподаватель, м.и. Ляшенко И.И. ___________________________

Кафедра «Информационные технологии»

Методические указания к лабораторным работам

По дисциплине: Численные методы

для студентов образовательных программ 6В06101 «Информатика», 6В06102 «Информационные системы», 6В06103 «Вычислительная техника и программное обеспечение», 6В01502 «Информатика»

Разработаны на основании Государственного общеобязательного стандарта послевузовского образования Республики Казахстан от 31.10.2018 г. №604 и Каталога элективных дисциплин образовательных программ 6В06103 «Вычислительная техника и программное обеспечение», 6В06102 «Информационные системы», 6В06101 «Информатика», 6В01502 «Информатика» (2018г.)

Рассмотрены на заседании кафедры «Информационные технологии»

Протокол №___ от _____________2019г.

Зав. кафедрой «Информационные технологии»

к.п.н., доц. _______________ А.Ж. Асаинова

Лабораторная работа №1

Тема: «Решение уравнения с одной переменной».

Цель: научиться с помощью ЭВМ отделять корни нелинейного уравнения с одной переменной, а также уточнять их с заданной точностью с помощью итерационных методов (метод половинного деления, метод простой итерации).

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

ЗНАТЬ:

- классификацию нелинейных уравнений с одной переменной (алгебраические, трансцендентные);

- виды методов решения такого рода уравнений: прямые (точные), приближенные (итерационные);

- алгоритм решения любого уравнения (имеются ли корни, их число, нахождение корней с заданной точностью);

УМЕТЬ:

- применять графический метод для отделения корней, т.е. установления достаточно малых окрестностей, в которых находится ровно один корень;

- применять метод половинного деления для уточнения корней на каждом отрезке отделения с заданной точностью 10^-6;

- приводить любое уравнение к итерационному виду;

- применять метод простой итерации для уточнения корней с заданной точностью 10^-3;

ИМЕТЬ ПРЕДСТАВЛЕНИЕ:

- о совокупности прямых и итерационных методов, применяющихся для приближенных вычислений;

- о применении теоремы Коши для существования корней нелинейного уравнения;

- об основных понятиях математического анализа (экстремум, производная, этапы исследования свойств функции).

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

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

В общем случае нелинейное уравнение можно записать в виде:

(1)

где функция F(x) определена и непрерывна на конечном или бесконечном интервале [a, b].

Любое число , обращающее функцию F(x) в нуль, т.е. , называется корнем уравнения (1). Число t называется корнем k-й кратности, если при x=t вместе с функцией F(x) равны нулю ее производные до (k-1) порядка включительно: .

Однократный корень называется простым.

Два уравнения F(x) и G(x) называются равносильными (эквивалентными), если всякое решение каждого из них является решением и для другого, т.е. множества решений этих уравнений совпадают.

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

Уравнение (1) называется алгебраическим, если функция является алгебраической функцией. Путем алгебраических преобразований из всякого алгебраического уравнения можно получить уравнение в канонической форме: , где a₀, a₁, …, a_n – коэффициенты уравнения, а x – неизвестное.

Например, уравнение может быть приведено к канонической форме: .

Если функция F(x) не является алгебраической, то уравнение (1) называется трансцендентным. Примерами трансцендентных уравнений могут быть: .

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

Решить уравнение – это значит установить:

1) имеет ли оно корни;

2) сколько корней;

3) найти значения корней с заданной точностью.

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

I этап. Отделение корней, т.е. нахождение достаточно малых окрестностей рассматриваемой области, в которых содержится одно значение корня.

II этап. Уточнение корней, т.е. вычисление корней с заданной степенью точности в некоторой окрестности.

Наиболее распространенными на практике численными методами решения уравнения (1) являются:

- метод половинного деления;

- метод хорд;

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

- комбинированный метод;

- метод простой итерации и т.д.

Отделение корней

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

(2)

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

Пример 1. Отделить корни уравнения .

Из графика следует, что уравнение имеет корень, принадлежащий отрезку [1; 1,5].

В сомнительных случаях графическое отделение корней необходимо подкрепить вычислениями. При этом следует придерживаться следующего алгоритма:

1) если неприрывная на отрезке [a, b] функция F(x) принимает на его концах значения разных знаков (т.е. ), то уравнение (1) имеет на этом отрезке по меньшей мере один корень;

2) если функция F(x) строго монотонна, то корень на отрезке [a, b] единственный.

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

Для отделения корней можно эффективно использовать ЭВМ.

Пусть имеется уравнение , причем можно считать, что все корни находятся на отрезке [A, B], в котором функция F(x) определена, неприрывна и . Требуется отделить корни уравнения, т.е. указать все отрезки [a, b] [A, B], содержащие по одному корню.

Будем вычислять значения F(x), начиная с точки x=A, двигаясь вправо с некоторым шагом h.

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

Результатом решения поставленной задачи будут выводимые на экран в цикле значения параметров x₁ и x₂ (концов выделенных отрезков).

Очевидно, что надежность рассмотренного подхода к отделению корней зависит как от характера функции F(x), так и от выбранной величины шага h. Действительно, при достаточно большом шаге h можно «проскочить» корень уравнения, т.е. получить одинаковые знаки значений функции в концах отрезка. Поэтому следует выбирать достаточно малые значения h.

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

Пусть уравнение (1) имеет на отрезке [a, b] единственный корень, причем функция F(x) на этом отрезке неприрывна. Разделим отрезок [a, b] пополам точкой . Если (что практически наиболее вероятно), то возможны два случая:

либо F(x) меняет знак на отрезке [a, c] (рисунок а);

либо F(x) меняет знак на отрезке [c, b] (рисунок b).

Выбирая в каждом случае тот из отрезков, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения. Рассмотренный метод можно использовать как метод решения уравнени с заданной точностью. Действительно, если на каком – то этапе процесса получен отрезок , содержащий корень, то, приняв приближенно , получим ошибку, не превышающую значения . Действительно, решая задачу отделения корня для примера 1 на ЭВМ, получим ответ: при А = 1.3; В = 1.5; погрешность Е = 0.0001 х ≈ 1.3995 D = 0.0001.