Решение нелинейных уравнений (стр. 1 из 2)
Содержание
Введение
1. Теоретическая часть
2. Метод половинного деления
3. Метод хорд
4. Метод Ньютона (касательных)
5. Метод простой итерации
Заключение
Список использованных источников
Введение
Основной целью реферата является изучение и сравнительный анализ итерационных методов решения нелинейных алгебраических и трансцендентных уравнений; реализация этих методов в виде машинных программ на языке высокого уровня и практическое решение уравнений на ЭВМ.
При разработке алгоритмов, входящих в состав математического обеспечения САПР, часто возникает необходимость в решении нелинейных уравнений вида
f(x) = 0, (1)
где функция f(x) определена и непрерывна на некотором конечном или бесконечном интервале a< x <b. В частности, в форме нелинейных уравнений представляются математические модели анализа статических свойств объектов проектирования или их элементов.
1. Теоретическая часть
Если функция f(x) представляет собой многочлен n-й степени вида
a0 + a1 x + a2 x2 + ... + an xn,
то уравнение (1) называется алгебраическим. Когда x находится под знаком трансцендентной функции (показательной, логарифмической, тригонометрической и т.п.), уравнение называется трансцендентным. Значение аргумента x*, при котором функция f(x) обращается в нуль, т.е. f(x*) = 0, называется корнем уравнения.
В общем случае для функции f(x) не существует аналитических формул для нахождения корней. Более того, их точное вычисление не всегда является необходимым. Это объясняется тем, что встречающиеся в инженерной практике уравнения часто содержат коэффициенты, величины которых имеют приближенные значения. В таких случаях решается задача определения корней с некоторой заранее заданной степенью точности.
В дальнейшем предполагаем, что уравнение (1) имеет только изолированные корни, т.е. для каждого из них существует некоторая окрестность, не содержащая других корней этого уравнения. Процесс нахождения изолированных действительных корней нелинейного уравнения включает два этапа:
1) отделение корней, т.е. нахождение интервалов [a, b], внутри которых содержится один и только один корень уравнения;
2) уточнение приближенных значений отдельных корней до заданной степени точности.
Этап отделения корней может быть выполнен различными способами. Во-первых, приближенное значение корня иногда бывает известно из физического смысла задачи. Во-вторых, для отделения корней может использоваться графический способ, основанный на построении графика функции y = f(x), где приближенные значения действительных корней уравнения f(x) = 0 соответствуют абсциссам точек пересечения или касания графика с осью 0x (y = 0).
Наиболее часто применяется метод отделения корней, основанный на следующем положении: если на концах некоторого интервала [a, b] значения непрерывной функции f(x) имеют разные знаки, т.е. f(a)f(b) <0, то на этом интервале уравнение (1) имеет хотя бы один корень. При этом корень является единственным, если производная функции f'(x) существует и сохраняет постоянный знак внутри интервала [a, b].
Рассмотрим простейший алгоритм отделения корней нелинейных уравнений, ориентированный на использование ЭВМ. Исходный интервал [a, b], на котором определена и непрерывна функция f(x), разбивается на n отрезков равной длины
(x0, x1), (x1, x2), ..., (xn -1, xn),
где x0 < x1< ...< xn и x0 = a, xn = b. Затем вычисляются значения функции f(xj) в точках xj (j =
) и выбирается отрезок (xi, xi+1), на концах которого функция имеет разные знаки, т.е. f(xi)f(xi+1) < 0. Если длина этого отрезка достаточно мала (можно предположить единственность корня), то считается, что корень отделен на интервале [a, b], где a = xi, b = xi+1. В противном случае границы исходного интервала сдвигаются, т.е. a = xi, b = xi + 1, и процедура повторяется.Необходимо отметить, что длина исходного интервала [a,b], на котором определена функция f(x), может изменяться в широких пределах. Поэтому число отрезков n, а также длина искомого интервала [a, b] являются переменными величинами, которые должны задаваться в каждом конкретном случае с учетом физического смысла решаемой задачи.
На втором этапе решения нелинейных уравнений полученные приближенные значения корней уточняются различными итерационными методами до некоторой заданной погрешности. Наиболее эффективные методы уточнения корней уравнения рассмотрены ниже.
2. Метод половинного деления
Для этого метода существенно, чтобы функция f(x) была непрерывна и ограничена в заданном интервале [a, b], внутри которого находится корень. Предполагается также, что значения функции на концах интервала f(a) и f(b) имеют разные знаки, т.е. выполняется условие f(a)f(b) <0.
Обозначим исходный интервал [a, b] как [a0, b0]. Для нахождения корня уравнения f(x) = 0 отрезок [a0, b0] делится пополам, т.е. вычисляется начальное приближение x0 = (a0 + b0)/2. Если f(x0) = 0, то значение x0 = x* является корнем уравнения. В противном случае выбирается один из отрезков [a0, x0] или [x0, b0], на концах которого функция f(x) имеет разные знаки, так как корень лежит в этой половине. Далее выбранный отрезок обозначается как [a1, b1], вновь делится пополам точкой x1 = (a1 + b1)/2 и т.д. В результате на некоторой итерации получается точный корень x* уравнения f(x) = 0, либо бесконечная последовательность вложенных отрезков [a0, b0], [a1, b1], ..., [ai, bi], ..., таких, что f(ai)f(bi) <0 (i =1, 2, ...), сходящихся к корню x*.
Если требуется определить корень x* с погрешностью e, то деление исходного интервала [a, b] продолжают до тех пор, пока длина отрезка [ai, bi] не станет меньше 2e, что записывается в форме условия
çbi - ai ç< 2e.
В этом случае середина последнего интервала [ai, bi] с требуемой степенью точности дает приближенное значение корня
x* » (ai + bi) / 2.
Метод половинного деления легко реализуется на ЭВМ и является наиболее универсальным среди итерационных методов уточнения корней. Его применение гарантирует получение решения для любой непрерывной функции f(x), если найден интервал, на котором она изменяет знак. В том случае, когда корни не отделены, будет найден один из корней уравнения. Метод всегда сходится, но скорость сходимости является небольшой, так как за одну итерацию точность увеличивается примерно в два раза. Поэтому на практике метод половинного деления обычно применяется для грубого нахождения корней уравнения, поскольку при повышении требуемой точности значительно возрастает объем вычислений.
3. Метод хорд
Пусть дано уравнение f(x) = 0, где f(x) - непрерывная функция, имеющая в интервале (a, b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке [a, b].
Идея метода хорд состоит в том, что на достаточно малом промежутке [a, b] дугу кривой y = f(x) можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай (рис. 1), когда первая и вторая производные имеют одинаковые знаки, т.е. f '(x)f ²(x) >0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид
.Приближение корня x = x1, для которого y = 0, определяется как
.Аналогично для хорды, проходящей через точки A1 и B, вычисляется следующее приближение корня
.В общем случае формула метода хорд имеет вид:
. (2)Если первая и вторая производные имеют разные знаки, т.е.
f '(x)f "(x) <0,
то все приближения к корню x* выполняются со стороны правой границы отрезка [a, b], как это показано на рис. 2, и вычисляются по формуле:
. (3)Выбор формулы в каждом конкретном случае зависит от вида функции f(x) и осуществляется по правилу: неподвижной является граница отрезка [a, b] изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (2) используется в том случае, когда f(b)f "(b) >0. Если справедливо неравенство f(a)f "(a) >0, то целесообразно применять формулу (3).
Рис. 1 Рис. 2
Рис. 3 Рис. 4
Итерационный процесс метода хорд продолжается до тех пор, пока не будет получен приближенный корень с заданной степенью точности. При оценке погрешности приближения можно пользоваться соотношением:
.Тогда условие завершения вычислений записывается в виде:
, (4)где e - заданная погрешность вычислений. Необходимо отметить, что при отыскании корня метод хорд нередко обеспечивает более быструю сходимость, чем метод половинного деления.
4. Метод Ньютона (касательных)
Пусть уравнение (1) имеет корень на отрезке [a, b], причем f '(x) и f "(x) непрерывны и сохраняют постоянные знаки на всем интервале [a, b].
Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной. Для этого выбирается некоторое начальное приближение корня x0 на интервале [a, b] и проводится касательная в точке C0(x0, f(x0)) к кривой y = f(x) до пересечения с осью абсцисс (рис. 3). Уравнение касательной в точке C0 имеет вид
y = f(x0) + f '(x0)×(x - x0).
Далее за приближение корня принимается абсцисса x1, для которой y = 0:
Затем проводится касательная через новую точку C1(x1, f(x1)) и определяется точка x2 ее пересечения с осью 0x и т.д. В общем случае формула метода касательных имеет вид: