40833

МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Лекция

Математика и математический анализ

Точное решение удается получить в исключительных случаях и обычно для нахождения корней уравнения применяются численные методы. Первая задача решается графическим методом: на заданном отрезке [ b] вычисляется таблица значений функции с некоторым шагом h строится ее график и определяются интервалы длиной h на которых находятся корни.1 в случаях и в значение корня совпадает с точкой экстремума функции и для нахождения таких корней можно использовать методы поиска минимума функции описанные в...

Русский

2013-10-22

748 KB

108 чел.

ТЕМА 5. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

5.1. Как решаются нелинейные уравнения

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

      f(x)=0.     (5.1)

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

1. Приближенное определение местоположения, характер и выбор интересующего нас корня.

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

Первая задача решается графическим методом: на заданном отрезке [a, b] вычисляется таблица значений функции с некоторым шагом h, строится ее график и определяются интервалы  длиной h, на которых находятся корни. На рис. 5.1 представлены три наиболее часто встречающиеся ситуации:

а) кратный корень:

б) простой корень:

в) вырожденный корень:  не существует, .

Как видно из рис. 5.1, в случаях «a» и «в» значение корня совпадает с точкой экстремума функции, и для нахождения таких корней можно использовать методы поиска минимума функции, описанные в теме 6.

На втором этапе вычисление значения корня с заданной точностью осуществляется одним из итерационных методов. При этом в соответствии с общей методологией m-шагового итерационного метода (cм. подразд. 1.5) на интервале        (, ), где находится интересующий нас корень x*, выбирается m начальных значений x0, x1, …, xm-1  (обычно x0 = a, x1 = b), после чего последовательно находятся члены (xm, xm+1, ..., xn-1, xn) рекуррентной последовательности порядка m по   правилу  до тех пор, пока . Последнее xn выбирается в качестве приближенного значения корня (x*  xn).

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

5.2. Итерационные методы уточнения корней

Метод простой итерации (MI)

Очень часто в практике вычислений встречается ситуация, когда уравнение (5.1) записано в виде, разрешенном относительно x:

     .      (5.2)

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

         ,     (5.3)

где  – произвольная, непрерывная, знакопостоянная функция (часто достаточно выбрать =const).  

В этом случае корни уравнения (5.2) являются также корнями (5.1) и наоборот.

Исходя из записи (5.2) члены рекуррентной последовательности в методе простой итерации вычисляются по закону

        .    (5.4)

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

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

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

Максимальный интервал (, ), для которого выполняется неравенство (5.5), называется областью сходимости. При выполнении условия (5.5) метод сходится, если начальное приближение x0 выбрано из области сходимости. При этом скорость сходимости погрешности  к нулю вблизи корня приблизительно такая же, как у геометрической прогрессии  со знаменателем , т.е. чем меньше q, тем быстрее сходимость, и наоборот. Поэтому при переходе от (5.1) к (5.2) функцию  в (5.3) выбирают так, чтобы выполнялось условие сходимости (5.5) для как можно большей области  и с наименьшим q. Удачный выбор этих условий гарантирует эффективность расчетов. Часто положительные результаты дает применение релаксации (см. подразд. 2.7). Схема алгоритма метода простой итерации представлена на рис. 5.3.

Метод Ньютона (MN)

Этот метод является модификацией метода простой итерации и часто называется методом касательных. Если f(x) имеет непрерывную производную, тогда, выбрав в (5.3) , получаем эквивалентное уравнение , в котором  Поэтому скорость сходимости рекуррентной последовательности метода Ньютона

        (5.6)

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

Из (5.6) видно, что этот метод одношаговый (m = 1), и для начала вычислений требуется задать одно начальное приближение x0 из области сходимости, определяемой неравен-ством . Метод Ньютона получил также второе название метод касательных благодаря геометрической иллюстрации его сходимости, представ-ленной на рис. 5.4. Этот метод позволяет находить как простые, так и кратные корни. Основной его недостаток – малая область сходимости и необходимость вычисления производной f'(x).

Метод секущих (MS)

Данный метод является модификацией метода Ньютона, позволяющей избавиться от явного вычисления производной путем ее замены приближенной формулой (4.2). Это эквивалентно тому, что вместо касательной на рис. 5.4 проводится секущая. Тогда вместо процесса (5.6) получаем

  .    (5.7)

Здесь h – некоторый малый параметр метода, который подбирается из условия наиболее точного вычисления производной (см. тему 4).

Метод одношаговый (m = 1), и его условие сходимости при правильном выборе h такое же, как у метода Ньютона.

Метод Вегстейна (MV)

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

(5.8)

Метод является двухшаговым (m = 2), и для начала вычислений требуется задать два начальных приближения . Лучше всего  (см. рис. 5.1). Метод Вегстейна сходится медленнее метода секущих, однако, требует в 2 раза меньшего числа вычислений f(x) и за счет этого оказывается более эффективным.

Этот метод иногда называется улучшенным методом простой итерации и в применении к записи уравнения в форме (5.2) имеет вид

  .     (5.9)

Схема алгоритма метода Вегстейна представлена на рис. 5.6.

Метод парабол (MP)

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

   .   (5.10)

Коэффициенты этого многочлена вычисляются по формулам

    

.  (5.11)

Полином (5.10) имеет два корня:

,

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

.  (5.12)

Метод трехшаговый (m = 3). Скорость сходимости его больше, чем у метода Вегстейна, однако, не лучше, чем у метода Ньютона вблизи корня. Схема алгоритма метода парабол представлена на рис. 5.8.

Метод деления отрезка пополам (MD)

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

Для разрывных функций, а также если не требуется быстрая сходимость, для нахождения простого корня на интервале (, ) применяют надежный метод деления отрезка пополам. Его алгоритм основан на построении рекуррентной

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

 1. Вычисляем .

 2. Вычисляем .

 3. Если   тогда   иначе .

 4. Если  тогда повторять с п.2.

 5. Вычисляем

 6. Конец.

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

5.3. Варианты заданий

По схеме на рис. 5.9 отладить программу определения всех корней функции f(x) в указанном интервале [a, b], использовать метод в соотвествии с полученным вариантом из табл. 5.1. 

Таблица 5.1

N вар.

f(x)

Интервал

метод

а

b

1

–2

2

MI

2

1

3

MN

3

1

8

MS

4

4

7

MV

5

4

8

MP

6

2

6

MD

7

3

9

MI

8

4

0

MN

9

12

5

MS

10

2

5

MV

11

6

2

MP

12

4

2

MD

13

7

3

MI

14

4

3

MN

15

4

4

MS

Примечание. В табл. 5.1 все функции на указанном интервале имеют три корня.

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

Расчет функции, а также метод нахождения корня оформить в виде отдельных подпрограмм. Вариант метода и функции взять из таблицы. Выбрать точность =10-4, а значение m по усмотрению.

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

5.4. Контрольные вопросы

1. Как решается задача нахождения корней?

2. В чем суть метода простой итерации и условие его сходимости?

3. Дайте геометрическую интерпретацию метода Ньютона.

4. В чем отличие метода Вегстейна от метода секущих?

5. Дайте геометрическую интерпретацию метода парабол.

PAGE  47


 

А также другие работы, которые могут Вас заинтересовать

20271. ОБОРУДОВАНИЕ GPRS 1.98 MB
  Между тем существуют некоторые технические особенности реализации оборудования GPRS среди которых следует выделить способ интеграции контроллеров пакетов PCU в подсистему базовых станции BSS. В качестве примера первого варианта организации оборудования GPRS может быть рассмотрено оборудование Alcatel в качестве второго Ericsson. ОБОРУДОВАНИЕ GPRS ПРОИЗВОДСТВА ALCATEL На рис.
20272. ОБОРУДОВАНИЕ GPRS. Сервисный узел поддержки услуг GPRS (SGSN) 1.58 MB
  Структурная схема SGSN В структуру SGSN входят: UNIX серверы блок маршрутизации интерфейсные модули интерфейсов на базе ОКС № 7 Gr Gd Gf Gs модули Gb интерфейса. UNIX серверы выполняют основные функции SGSN такие как управление мобильностью управление сессиями тарификация функции протокола GTP и др.Основные функции SGSN разделяются на две плоскости рис.
20273. Высокое качество передачи речевой информации 133.5 KB
  К началу 1994 года сети основанные на рассматриваемом стандарте имели уже 1. Воистину GSM шагает по планете в настоящее время телефоны этого стандарта имеют около 200 миллионов человек а GSMсети можно найти по всему миру. ОСНОВНЫЕ ЧАСТИ СИСТЕМЫ GSM ИХ НАЗНАЧЕНИЕ И ВЗАИМОДЕЙСТВИЕ ДРУГ С ДРУГОМ Начнем с самого сложного и пожалуй скучного рассмотрения скелета или как принято говорить блоксхемы сети.
20274. ПОЛЬЗОВАТЕЛЬСКИЙ ИНТЕРФЕЙС МОБИЛЬНОЙ СТАНЦИИ 82.5 KB
  Примитивы ввода Спецификацией GSM предусмотрен следующий набор элементарных процедур ввода: 1 2 то же что и ABC 3 то же что и DEF 4 то же что и GHI 5 то же что и JKL 6 то же что и MNO 7 то же что и PQRS 8 то же что и TUV 9 то же что и WXYZ 0 то же что и SELECT ACCEPT SEND END для ввода номера в международном формате Код Страны Номер Процедура выбора страны PLMN Процедура ввода дополнительных данных о вызове голос факс данные синхронный асинхронный режим передачи и т. Индикатор...
20275. СЕТЕВЫЕ АСПЕКТЫ УПРАВЛЕНИЯ СПС 96 KB
  Третий уровень протокола обмена сигналами GSM подразделяется на три подуровня: Подуровень управления радио ресурсами Radio Resources Management. Спецификация MAP это одна из самых объемных частей в рекомендациях GSM.В системах GSM существуют четыре основных типа таких процедур: Каналы тайм слоты принадлежат одной соте. Очень важным аспектом GSM является тот факт что MSC так называемая якорная MSC является ответственной за большинство функций имеющих непосредственное отношение к соединению за исключением внутренних BSC хандоверов...
20276. Оборудование подсистемы коммутации (SSS) 254 KB
  Подсистема коммутации системы SSS в рамках СМЕ20 реализована на базе известной коммутационной системы АХЕ10. Каждая подсистема разделена на функциональные блоки. Подсистемы APT Подсистема Наименование подсистемы Функции Назначение станции в сети GSM CCS Common Channel Signalling Subsystem ОКС Управление ОКС № 7 MSC GMSC BSC HLR CHS Charging Subsystem Тарификация Обеспечение тарификации и учет стоимости MSC DTS Data Transmission Subsystem Передача данных Пакетирование сообщений при передаче данных в среде ISDN по Dканалу MSC ESS...
20277. ЯПОНИЯ в 20-30-е гг.20в. основные черты экономического и политического развития 16.94 KB
  В годы первой мировой войны и после нее происходил значительный экономический рост Японии. Политическая власть в Японии принадлежала прежде всего императору совету старейшин генро Тайному совету и правительству. Фашизация Японии. преодолевались в Японии за счет милитаризации экономики т.
20278. Причины и характер войны 19.19 KB
  Разгром Франции. Что касается поведения Англии и Франции то дело тут было более сложным. Объясняется это тем что Англия к войне на суше как военноморская держава подготовлена не была а правительство Франции в свою очередь ориентировалось на Англию. На поведении Англии и Франции отразилось также подписание 28 сентября 1939 г.
20279. КОРЕННОЙ ПЕРЕЛОМ В ХОДЕ ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ И ВТОРОЙ МИРОВОЙ ВОЙНЫ 19.04 KB
  КОРЕННОЙ ПЕРЕЛОМ В ХОДЕ ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ И ВТОРОЙ МИРОВОЙ ВОЙНЫ Вспомните. Начался коренной перелом в ходе Великой Отечественной и второй мировой войны. Битва под Курском знаменательное событие второй мировой войны. Победа на Курской дуге и успешное наступление завершили коренной перелом в ходе Великой Отечественной и второй мировой войны.