Решение трансцендентных уравнений методом дихотомий.

Решение трансцендентных уравнений методом дихотомий.

F (x, a 1, a 2,..., a k) = 0

(3.1)

где F - заданная непрерывная функция;

x – неизвестная величина, подлежащая определению;

a ₁, a ₂,..., a _k – известные параметры функции F.

Решить уравнение (3.1) - это значит найти такое значение (или такие значения) неизвестной x, при которых уравнение (3.1) превращается в тождество. Эти значения x называются корнями уравнения (3.1). Существует несколько различных методов численного решения трансцендентных уравнений, но все они предполагают выполнение двух этапов: первый из них называется " отделение корней ", второй - " уточнение корней " Отделение корней: На данном этапе определяются те интервалы области изменения переменной x, в каждом из которых расположен один и только один корень уравнения (3.1). По сути дела на этом этапе определяются грубые приближения значений x с погрешностью, определяемой длиной каждого найденного интервала При выполнении этого этапа с использованием ЭВМ обычно проводится "табу­лирование " функции F (x, a ₁, a ₂,..., a _k), т.е. построение таблицы ее значений при различных значе­ниях x, следующих друг за другом с некоторым шагом h Метод Дихотоми Пусть на этапе отделения корней получены две точки A и B (A<B), между которыми находится корень уравнения (3.1), т.е. такие точки, в которых знаки значений функ­ции F (x) противоположны (см. рис.3.2): sign F (A) ¹ sign F (B).

Метод дихотомии, называемый еще методом половинного деления, заключается в следующем:

1) определяется середина отрезка [ A, B ]:

;

(3.2)

2) вычисляется значение функции в этой точке - F (P) и его знак sign F (P);

3) корень уравнения (3.1) находится в той половине отрезка [ A, B ], на концах которой функция F (x) имеет разные знаки. Если это будет половинка [ A, P ], то перенесем точку B в точку P; если же половинка [ P, B ], то перенесем точку A в точку P. Благодаря этой операции длина отрезка [ A, B ], на котором находится корень уравнения, уменьшилась вдвое, т.е. можно сказать, что значение корня определено с точностью до длины полученного отрезка.

Каждое новое повторение действий 1,2,3 будет давать все более точные значения корня уравнения. Повторение этого процесса следует прекращать, когда длина отрезка [ A, B ] станет меньше заранее заданного значения , являющегося в данном случае ошиб­кой ограничения, т.е. неравенство

B - A <

(3.3)

является критерием окончания вычислительного процесса

Рис.3.2. Геометрическая интерпретация метода

дихотомии

2.Решение трансцендентных уравнений методом хорд.

известны две точки A и B (A<B),для которых sign F (A) ¹ sign F (B). В методе хорд, в отличие от метода дихотомий, в ка­чес­тве очередного приближения P берется точка пересечения с осью абсцисс хорды, соединяющей точки (A, F (A)) и (B, F (B)).

 

Уравнение прямой, проходящей через эти две точки запишем в виде: Y (x) = k x + c.

Коэффициенты k и c определяются из условий:

F (A) = k A + c; F (B) = k B + c.

Решая эту систему из двух уравнений, получим:

; c = F (A) - k A.

Точка P пересечения этой прямой с осью ОX определяется из уравнения

kP + c = 0.

Решая его, окончательно получаем:

.

(3.4)

В методе хорд нельзя использовать в качестве критерия окончания вычислительного процесса неравенство (3.3), так как, как видно из рис.3.4, величина B – A не стремится к нулю. В данном методе, как и в рассматриваемых ниже, вычислительный процесс следует прекращать при выполнении неравенства

,

(3.5)

т.е. если расстояние между двумя соседними приближениями к корню меньше заранее заданной величины . Алгоритм метода хорд, следовательно, отличается от алгоритма метода дихотомий формулой вычисления приближения P (вместо (3.2) использется (3.4))и критерием окончания вычислительного процесса (вместо (3.3) использется (3.5)).

Метод наименьших квадратов

Последовательность действий при аппроксимации экспоненциальной зависимостью (5.21) выглядит так:

1) вычисление логарифмов значений аппроксимируемой функции ;

2) вычисление коэффициентов и по формулам (5.23);

3) вычисление коэффициентов c и d, по формулам (5.24);

4) вычисление значений по формуле (5.21).

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

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

Рис.5.5.

Рис.5.6.

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

Q = = .

(5.11)

Метод построения аппроксимирующей функции (x) из условия минимума величины Q называется методом наименьших квадратов (далее - МНК).

Наиболее распространен способ выбора функции (x) в виде линейной комбинации

(x) = с 0 0(x) + с 1 1(x) + … + сm m(x),

(5.12)

где ₀(x), ₁(x), …, _m(x) - базисные функции; ;

с _0, с _1, …, с_m - коэффициенты, определяемые при минимизации величины Q.

При обработке экспериментальных данных, полученных с погрешностью в каждой узловой точке, обычно начинают с аппроксимации функцией , представленной одной-двумя базисными функциями. После определения коэффициентов с _k вычисляется ве­ли­чина Q по формуле (5.11). Если окажется, что , то необходимо расширить базис добавлением новых базисных функций . Расширение базиса необходимо про­­должать до тех пор, пока не выполнится условие .

Выбор конкретных базисных функций зависит от свойств аппроксимируемой функции f (x), таких, как периодичность, экспоненциальный или логарифмический характер, симметричность, наличие асимптот и т.д. Различные варианты базисов рассматриваются достаточно подробно в [1]. Здесь рассмотрим лишь частный случай, когда аппрксимирующая функция представлена двумя базисными функциями, т.е.

 

Рассмотрим частный случай линейной аппроксимации, т.е. когда график аппро­кси­мирующей функции есть прямая линия: . В этом случае базисные функции имеют вид: , . Тогда из (5.19) получаем:

, ,

где символ "надчеркивание" обозначает среднее значение:

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

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

.

(5.21)

Прологарифмируем значения аппроксимируемой функции f (x) в узловых точках:

, i=0,1,2,…,n

и для реализации по формулам (5.20) найдем линейную аппроксимирующую функцию

(5.22)

Формулы (5.20) выглядят при этом так:

.

(5.23)

Чтобы теперь осуществить переход от функции к функции , надо пропотенцировать обе части равенства (5.22):

Величину обозначим , а коэффициенты с и d, входящие в (5.21), вычисляются по формулам:

.

(5.24)

 

Методы прямоугольников

Данные методы относятся к простейшим из класса методов Ньютона-Котеса. В них подынтегральная функция f(x) на каждом интервале разбиения заменяется полиномом ну-левой степени, т.е. константой. Такая замена является неоднозначной, т.к. константу можно выбрать равной значению f(x) в любой точке данного интервала разбиения.

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

Левые	Средние	Правые

Введем следующие обозначения: точку a на оси OX обозначим через x ₀, точку b - через x _n, а точки разбиения промежутка [ a,b ] - через x ₁, x ₂,..., x _n-1. Предполагается, что длина интервала разбиения постоянна на всем [ a,b ]. Обозначим ее через h:

; x _i = x _i-1 + h, i =1,2,..., N.

Тогда в методе левых прямоугольников площадь каждого i -го прямоугольника

S i = h f (x i), i = 0,1,2,..., n -1,

(6.2)

а для всего промежутка [ a,b ]:

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

S i = h f (x i), i = 1,2,..., n; .

(6.3)

и в методе средних прямоугольников

S i = h ), i = 0,1,2,..., n -1; ,

(6.4)

где , i = 0,1,2,..., n -1.

Приведенные формулы для S являются вычислительными формулами методов прямоугольников.

На рис.6.5. приведена блок-схема вычисления определенного интеграла методом средних прямоугольников.

Рис.6.5. Алгоритм метода средних прямоугольников

Алгоритмы для методов левых и правых прямоугольников отличаются от изображенного на рис.6.5 лишь одним блоком (он выделен жирной линией). Для метода левых прямоугольников здесь должно стоять X=A, для метода правых прямоугольников должно быть X=A+h.

Оценим точность этих методов. В методе средних прямоугольников для каждого интервала разбиения получаем c учетом выражения для S _i в (6.4):

.

(6.5)

Для оценки R _i разложим функцию f (x) в ряд Тейлора около средней точки

(6.6)

В малой окрестности точки этот ряд с высокой точностью представляет функцию f (x) при небольшом количестве членов разложения. Поэтому, подставляя под знак интеграла вместо f (x) ее тейлоровское разложение (6.6) и интегрируя его почленно, можно вычислить интеграл с любой наперед заданной точностью. T.е. точное значение интеграла на интервале [ x _i, x _i+1] рав­но:

Подставим пределы интегрирования:

или, так как :

Все члены полученного при интегрировании ряда, имеющие (x - x _i) в четной степени, обращаются в нуль. Поэтому получаем:

(6.7)

Сравнивая (6.5) и (6.7), можно записать выражение для погрешности R _i:

При малой величине шага интегрирования h основной вклад в значение R _i дает первое слагаемое, которое называется главным членом погрешности вычисления интеграла на интервале [ x _i, x _i+1] и обозначается R _0i:

.

(6.8)

Главный член полной погрешности для интеграла на всем промежутке [ a,b ] определится как сумма:

.

(6.9)

Здесь использован тот же метод средних прямоугольников, но для функции .

Степень шага h, которой пропорциональна величина R ₀, называется порядком метода интегрирования. Как видно из (6.9 ), метод средних прямоугольников имеет второй порядок.

Аналогично проведем оценку метода левых прямоугольников. Разложим подынтегральную функцию в ряд Тейлора в окрестности точки x = x _i:

Интегрируя это разложение почленно на интервале [ x _i, x _i+1] получаем

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

.

(6.10)

Тогда на всем промежутке интегрирования [ a,b ] главный член погрешности R ₀ получается суммированием частичных погрешностей R _0i:

,

(6.11)

т.е. метод левых прямоугольников имеет первый порядок. Метод правых прямоугольников также имеет первый порядок.

Сравнение (6.9) и (6.11) показывает, что метод средних прямоугольников имеет меньшую погрешность по сравнению с методом левых или правых прямоугольников и за счет коэффициента в знаменателе (24 > 2), и за счет интеграла от производной, т.к. для большинства функций выполняется неравенство

.

Следовательно, использование метода средних прямоугольников является предпочтительным, но использовать его удается не всегда. Если значения f (x) определяются из эксперимента в дискретном наборе узлов, то метод средних прямоугольников напрямую при­менить нельзя из-за отсутствия значений f (x) в срединных точках. В этой ситуации приходится применять либо какие-нибудь средства интерполяции, что приводит к дополнительным расходам машинного времени и памяти, либо другие методы численного интегрирования.

Метод трапеций

В этом методе подынтегральная функция f (x) на интервале [ x _i, x _i+1] заменяется полиномом первой степени, т.е. наклонной прямой линией. Обычно эта прямая проводится через значения f (x) на границах интервала (рис.6.6). В этом случае приближенное значение частичного интеграла определяется площадью трапеции:

Рис.6.6. Геометрическая интерпретация метода трапеций

, т.е. , а численное значение интеграла на всем [ a,b ] . Это вычислительная формула метода трапеций.

(6.12)     (6.13)

Блок-схему алгоритма метода трапеций предлагается студентам разработать самим.

Оценим погрешность R _i. Для этого разложим функцию f (x) в ряд Тейлора около точки x _i:

(6.14)

Тогда

(6.15)

С помощью разложения (6.14) вычислим подынтегральную функцию в точке x _i+ h:

откуда

(6.16)

Подставляя произведение (6.16) в выражение (6.15), получим

(6.17)

Сравнивая (6.12) и (6.17), получаем выражение для главного члена погрешности частичного интеграла

.

Тогда главный член полной погрешности метода трапеций имеет вид

,

(6.18)

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

 

Вопросы по 10 баллов

Различие между прямыми и итерационными методами численного решения задач. Примеры.

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

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

Два этапа численного решения трансцендентных уравнений.
Цель и сущность этапа отделения корней при решении трансцендентных уравнений.

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

Метод трапеций

В этом методе подынтегральная функция f (x) на интервале [ x _i, x _i+1] заменяется полиномом первой степени, т.е. наклонной прямой линией. Обычно эта прямая проводится через значения f (x) на границах интервала (рис.6.6). В этом случае приближенное значение частичного интеграла определяется площадью трапеции:

Рис.6.6. Геометрическая интерпретация метода трапеций

, т.е. , а численное значение интеграла на всем [ a,b ] . Это вычислительная формула метода трапеций.

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

На рис.6.5. приведена блок-схема вычисления определенного интеграла методом средних прямоугольников.

Решение трансцендентных уравнений методом дихотомий.

F (x, a 1, a 2,..., a k) = 0

(3.1)

где F - заданная непрерывная функция;

x – неизвестная величина, подлежащая определению;

a ₁, a ₂,..., a _k – известные параметры функции F.

Решить уравнение (3.1) - это значит найти такое значение (или такие значения) неизвестной x, при которых уравнение (3.1) превращается в тождество. Эти значения x называются корнями уравнения (3.1). Существует несколько различных методов численного решения трансцендентных уравнений, но все они предполагают выполнение двух этапов: первый из них называется " отделение корней ", второй - " уточнение корней " Отделение корней: На данном этапе определяются те интервалы области изменения переменной x, в каждом из которых расположен один и только один корень уравнения (3.1). По сути дела на этом этапе определяются грубые приближения значений x с погрешностью, определяемой длиной каждого найденного интервала При выполнении этого этапа с использованием ЭВМ обычно проводится "табу­лирование " функции F (x, a ₁, a ₂,..., a _k), т.е. построение таблицы ее значений при различных значе­ниях x, следующих друг за другом с некоторым шагом h Метод Дихотоми Пусть на этапе отделения корней получены две точки A и B (A<B), между которыми находится корень уравнения (3.1), т.е. такие точки, в которых знаки значений функ­ции F (x) противоположны (см. рис.3.2): sign F (A) ¹ sign F (B).

Метод дихотомии, называемый еще методом половинного деления, заключается в следующем:

1) определяется середина отрезка [ A, B ]:

;

(3.2)

2) вычисляется значение функции в этой точке - F (P) и его знак sign F (P);

3) корень уравнения (3.1) находится в той половине отрезка [ A, B ], на концах которой функция F (x) имеет разные знаки. Если это будет половинка [ A, P ], то перенесем точку B в точку P; если же половинка [ P, B ], то перенесем точку A в точку P. Благодаря этой операции длина отрезка [ A, B ], на котором находится корень уравнения, уменьшилась вдвое, т.е. можно сказать, что значение корня определено с точностью до длины полученного отрезка.

Каждое новое повторение действий 1,2,3 будет давать все более точные значения корня уравнения. Повторение этого процесса следует прекращать, когда длина отрезка [ A, B ] станет меньше заранее заданного значения , являющегося в данном случае ошиб­кой ограничения, т.е. неравенство

B - A <

(3.3)

является критерием окончания вычислительного процесса

Рис.3.2. Геометрическая интерпретация метода

дихотомии

2.Решение трансцендентных уравнений методом хорд.

известны две точки A и B (A<B),для которых sign F (A) ¹ sign F (B). В методе хорд, в отличие от метода дихотомий, в ка­чес­тве очередного приближения P берется точка пересечения с осью абсцисс хорды, соединяющей точки (A, F (A)) и (B, F (B)).

 

Уравнение прямой, проходящей через эти две точки запишем в виде: Y (x) = k x + c.

Коэффициенты k и c определяются из условий:

F (A) = k A + c; F (B) = k B + c.

Решая эту систему из двух уравнений, получим:

; c = F (A) - k A.

Точка P пересечения этой прямой с осью ОX определяется из уравнения

kP + c = 0.

Решая его, окончательно получаем:

.

(3.4)

В методе хорд нельзя использовать в качестве критерия окончания вычислительного процесса неравенство (3.3), так как, как видно из рис.3.4, величина B – A не стремится к нулю. В данном методе, как и в рассматриваемых ниже, вычислительный процесс следует прекращать при выполнении неравенства

,

(3.5)

т.е. если расстояние между двумя соседними приближениями к корню меньше заранее заданной величины . Алгоритм метода хорд, следовательно, отличается от алгоритма метода дихотомий формулой вычисления приближения P (вместо (3.2) использется (3.4))и критерием окончания вычислительного процесса (вместо (3.3) использется (3.5)).