Регула ложная

В математике regula falsi , метод ложного положения или метод ложного положения — очень старый метод решения уравнения с одним неизвестным; этот метод, в измененной форме, используется до сих пор. Проще говоря, этот метод — это метод проб и ошибок , при котором используются тестовые («ложные») значения переменной, а затем тестовое значение корректируется в соответствии с результатом. Иногда это также называют «угадай и проверь». Версии метода существовали до появления алгебры и использования уравнений .

В качестве примера рассмотрим задачу 26 в папирусе Ринда , в которой требуется решение (записанное в современной записи) уравнения $x + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠х/4⁠ = 15.$ Это решается с помощью ложной позиции.^[1] Сначала предположим, что $x = 4$ , чтобы получить слева 4 + ⁠4/4⁠ = 5 . Это предположение является хорошим выбором, поскольку оно дает целое значение. Однако 4 не является решением исходного уравнения, поскольку дает значение, которое в три раза меньше. Чтобы компенсировать это, умножьте $x$ (текущее значение которого равно 4) на 3 и подставьте снова, чтобы получить 12 + ⁠12/4⁠ = 15 , проверяя, что решение равно $x = 12$ .

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

Два исторических типа

Исторически можно выделить два основных типа метода ложного положения: простое ложное положение и двойное ложное положение .

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

ax=b,

если известны $a$ и $b . Метод начинается с использования тестового входного значения$ $x'$ и нахождения соответствующего выходного значения $b'$ путем умножения: $ax' = b'$ . Затем правильный ответ находится путем пропорциональной корректировки, $x = ⁠ б / б' ⁠ х'$ .

Двойное ложное положение направлено на решение более сложных задач, которые можно записать алгебраически в виде: определить $x$ такое, что

f(x)=ax+c=0,

если известно, что

f(x_{1})=b_{1},\qquad f(x_{2})=b_{2}.

Двойная ложная позиция математически эквивалентна линейной интерполяции . Используя пару тестовых входов и соответствующую пару выходов, результат этого алгоритма определяется как, ^[2]

x={\frac {b_{1}x_{2}-b_{2}x_{1}}{b_{1}-b_{2}}},

запоминалось и выполнялось наизусть. Действительно, правило, данное Робертом Рекордом в его «Основании искусств» (ок. 1542 г.), таково: ^[2]

Гессе, как оказалось, руководит этой работой.
По совпадению вы можете продолжить.
И сначала задайте вопрос,
Хотя правды в этом нет.
Такая ложь - очень хорошее основание,
Эта истина вскоре будет найдена.
От многих лет до многих лет,
От до fewe берите также и до fewe.
Слишком много радости, чтобы снова стать немногочисленной,
К немногим добавить еще много простого.
В перекрестках умножают противоположное,
Вся правда ложью ради нахождения.

Для аффинной линейной функции ,

f(x)=ax+c,

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

История

Простая техника ложного положения встречается в клинописных табличках древней вавилонской математики и в папирусах древней египетской математики . ^[3]^[1]

Двойная ложная позиция возникла в поздней античности как чисто арифметический алгоритм. В древнекитайском математическом тексте под названием «Девять глав о математическом искусстве» (九章算術) ^[4] , датируемом периодом с 200 г. до н. э. по 100 г. н. э., большая часть главы 7 была посвящена алгоритму. Там процедура была обоснована конкретными арифметическими аргументами, а затем применена творчески к широкому спектру задач на сюжет, включая задачу, включающую то, что мы бы назвали секущими линиями на коническом сечении . Более типичным примером является эта задача о «совместной покупке», включающая условие «избытка и дефицита»: ^[5]

Теперь предмет покупается сообща; каждый вносит 8 [монет], излишек 3; каждый вносит 7, дефицит 4. Скажите: Количество человек, цена предмета, какова стоимость каждого? Ответ: 7 человек, цена предмета 53. ^[6]

Между IX и X веками египетский математик Абу Камиль написал ныне утерянный трактат об использовании двойной ложной позиции, известный как Книга двух ошибок ( Kitāb al-khaṭāʾayn ). Старейшее сохранившееся сочинение о двойной ложной позиции с Ближнего Востока принадлежит Кусте ибн Луке (X век), арабскому математику из Баальбека , Ливан . Он обосновал технику формальным геометрическим доказательством в евклидовом стиле . В традиции средневековой мусульманской математики двойная ложная позиция была известна как hisāb al-khaṭāʾayn («расчет по двум ошибкам»). Она использовалась на протяжении столетий для решения практических задач, таких как коммерческие и юридические вопросы (разделы имущества в соответствии с правилами наследования Корана ), а также чисто развлекательных задач. Алгоритм часто запоминался с помощью мнемоники , например, стиха, приписываемого Ибн аль-Ясамину , и диаграмм весов, объясненных аль-Хассаром и Ибн аль-Банной , все трое были математиками марокканского происхождения. ^[7]

Леонардо Пизанский ( Фибоначчи ) посвятил главу 13 своей книги Liber Abaci (1202 г. н. э.) объяснению и демонстрации использования двойной ложной позиции, назвав метод regulis elchatayn в честь метода al-khaṭāʾayn , который он узнал из арабских источников. ^[7] В 1494 году Пачоли использовал термин el cataym в своей книге Summa de arithmetica , вероятно, заимствовав термин у Фибоначчи. Другие европейские авторы последовали за Пачоли и иногда давали перевод на латынь или на разговорный язык. Например, Тарталья переводит латинизированную версию термина Пачоли на разговорный язык «ложные позиции» в 1556 году. ^[8] Термин Пачоли почти исчез в европейских работах XVI века, и эта техника носила разные названия, такие как «Правило ложности», «Правило положения» и «Правило ложной позиции». Regula Falsi появляется как латинизированная версия Rule of False еще в 1690 году. ^[2]

Несколько европейских авторов XVI века чувствовали необходимость извиниться за название метода в науке, которая стремится найти истину. Например, в 1568 году Хамфри Бейкер говорит: ^[2]

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

Численный анализ

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

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

Дано уравнение, переместите все его члены в одну сторону так, чтобы оно имело вид $f (x) = 0$ , где $f$ — некоторая функция неизвестной переменной $x$ . Значение $c$ , удовлетворяющее этому уравнению, то есть $f (c) = 0$ , называется корнем или нулем функции $f$ и является решением исходного уравнения. Если $f$ — непрерывная функция и существуют две точки $a 0$ и $b 0$ такие, что $f (a 0)$ и $f (b 0)$ имеют противоположные знаки, то по теореме о промежуточном значении функция $f$ имеет корень в интервале $(a 0, b 0)$ .

Существует множество алгоритмов поиска корней , которые можно использовать для получения приближений к такому корню. Одним из наиболее распространенных является метод Ньютона , но он может не найти корень при определенных обстоятельствах и может быть вычислительно затратным, поскольку требует вычисления производной функции . Необходимы $другие$ методы, и одним из общих классов методов являются методы двухточечной скобки . Эти методы $действуют$ $путем$ $создания$ последовательности сжимающихся интервалов $[ak, bk]$ на $k$ -м шаге, так что $(ak,$ $bk$ $)$ содержит корень $f$ .

Методы двухточечного брекетинга

Эти методы начинаются с двух значений $x$ , изначально найденных методом проб и ошибок, при которых $f (x)$ имеет противоположные знаки. При предположении непрерывности корень $f$ гарантированно лежит между этими двумя значениями, то есть эти значения «заключают» корень в скобки. Затем выбирается точка строго между этими двумя значениями и используется для создания меньшего интервала, который все еще заключает в скобки корень. Если выбрана точка $c$ , то меньший интервал идет от $c$ до конечной точки, где $f (x)$ имеет знак, противоположный знаку $f (c)$ . В маловероятном случае, когда $f (c) = 0$ , корень найден, и алгоритм останавливается. В противном случае процедура повторяется столько раз, сколько необходимо для получения приближения к корню с любой желаемой точностью.

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

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

Простейший вариант, называемый методом бисекции , вычисляет оценку решения как середину интервала брекетинга. То есть, если на шаге $k$ текущий интервал брекетинга равен $[a k, b k]$ , то новая оценка решения $c k$ получается следующим образом:

c_{k}={\frac {a_{k}+b_{k}}{2}}.

Это гарантирует, что $c k$ находится между $a k$ и $b k$ , тем самым гарантируя сходимость к решению.

Поскольку длина интервала взятия в скобки уменьшается вдвое на каждом шаге, ошибка метода бисекции в среднем уменьшается вдвое с каждой итерацией. Таким образом, каждые 3 итерации метод выигрывает примерно в 2 ^{3 раза} , т.е. примерно на десятичный знак, в точности.

Theрегула ложная(ложное положение) метод

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

Метод regula falsi вычисляет новую оценку решения как $x$ -пересечение отрезка прямой, соединяющего конечные точки функции на текущем интервале взятия в скобки. По сути, корень аппроксимируется путем замены фактической функции отрезком прямой на интервале взятия в скобки, а затем использования классической формулы двойной ложной позиции на этом отрезке прямой. ^[9]

Точнее, предположим, что в $k$ $-й итерации интервал скобок равен (ak$ $,$ bk $) . Постройте прямую через$ точки $($ $ak, f (ak)) и$ ( $bk, f (bk$ $)$ $)$ $,$ как показано на рисунке. Эта прямая является секущей или хордой графика функции $f$ . В форме $точки$ -наклона ее уравнение задается как

y-f(b_{k})={\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(x-b_{k}).

Теперь выберем $c k$ в качестве точки пересечения этой линии с осью $x$ , то есть значения $x,$ для которого $y = 0$ , и подставим эти значения, чтобы получить

f(b_{k})+{\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(c_{k}-b_{k})=0.

Решение этого уравнения относительно c _k дает:

c_{k}=b_{k}-f(b_{k}){\frac {b_{k}-a_{k}}{f(b_{k})-f(a_{k})}}={\frac {a_{k}f(b_{k})-b_{k}f(a_{k})}{f(b_{k})-f(a_{k})}}.

Эта последняя симметричная форма имеет вычислительное преимущество:

По мере приближения к решению $a k$ и $b k$ будут очень близки друг к другу и почти всегда одного знака. Такое вычитание может привести к потере значимых цифр. Поскольку $f (b k)$ и $f (a k)$ всегда имеют противоположные знаки, «вычитание» в числителе улучшенной формулы фактически является сложением (как и вычитание в знаменателе).

На итерации номер $k$ число $c k$ вычисляется, как указано выше, а затем, если $f (a k)$ и $f (c k)$ имеют одинаковый знак, устанавливаем $a k + 1 = c k$ и $b k + 1 = b k$ , в противном случае устанавливаем $a k + 1 = a k$ и $b k + 1 = c k$ . Этот процесс повторяется до тех пор, пока корень не будет достаточно хорошо аппроксимирован.

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

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

Анализ

Поскольку начальные конечные точки $a 0$ и $b 0$ выбраны таким образом, что $f (a 0)$ и $f (b 0)$ имеют противоположные знаки, на каждом шаге одна из конечных точек будет приближаться к корню $f$ . Если вторая производная $f$ имеет постоянный знак (то есть нет точки перегиба ) на интервале, то одна конечная точка (та, где $f$ также имеет тот же знак) останется фиксированной для всех последующих итераций, в то время как сходящаяся конечная точка будет обновляться. В результате, в отличие от метода бисекции , ширина скобки не стремится к нулю (если только ноль не находится в точке перегиба, вокруг которой $sign(f) = -sign(f ")$ ). Как следствие, линейное приближение к $f (x)$ , которое используется для выбора ложного положения, не улучшается так быстро, как это возможно.

Одним из примеров этого явления является функция

f(x)=2x^{3}-4x^{2}+3x

на начальной скобке [−1,1]. Левый конец, −1, никогда не заменяется (он не меняется сначала, а после первых трех итераций $f "$ отрицателен на интервале), и, таким образом, ширина скобки никогда не опускается ниже 1. Следовательно, правая конечная точка приближается к 0 с линейной скоростью (количество точных цифр растет линейно, со скоростью сходимости 2/3). ^{[ необходима цитата ]}

Для разрывных функций этот метод может только, как ожидается, найти точку, где функция меняет знак (например, при $x = 0$ для $1/ x$ или знаковой функции ). В дополнение к изменениям знака, метод также может сходиться к точке, где предел функции равен нулю, даже если функция не определена (или имеет другое значение) в этой точке (например, при $x = 0$ для функции, заданной как $f (x) = abs(x) - x 2$ , когда $x \neq 0$ и как $f (0) = 5$ , начиная с интервала [-0,5, 3,0]). Математически возможно, что с разрывными функциями метод не сможет сходиться к нулевому пределу или смене знака, но это не проблема на практике, поскольку для того, чтобы застрять на сходящейся точке разрыва, где знак не меняется, например, при $x = \pm1$ в

f(x)={\frac {1}{(x-1)^{2}}}+{\frac {1}{(x+1)^{2}}}.

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

Улучшения врегула ложная

Хотя regula falsi всегда сходится, обычно значительно быстрее, чем бисекция, существуют ситуации, которые могут замедлить его сходимость – иногда до запретительной степени. Эта проблема не является уникальной для regula falsi : кроме бисекции, все методы численного решения уравнений могут иметь проблему медленной сходимости или отсутствия сходимости при некоторых условиях. Иногда метод Ньютона и метод секущих расходятся вместо того, чтобы сходиться – и часто делают это при тех же условиях, что и замедляют сходимость regula falsi .

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

Режим отказа Regula falsi легко обнаружить: одна и та же конечная точка сохраняется дважды подряд. Проблема легко устраняется выбором вместо нее измененной ложной позиции, выбранной для избежания замедлений из-за этих относительно необычных неблагоприятных ситуаций. Было предложено несколько таких улучшений regula falsi ; два из них, алгоритм Иллинойса и алгоритм Андерсона–Бьорка, описаны ниже.

Алгоритм Иллинойса

Алгоритм Иллинойса делит пополам значение $y$ сохраненной конечной точки в следующем вычислении оценки, когда новое значение $y$ (то есть $f (c k$ )) имеет тот же знак, что и предыдущее ( $f (c k - 1$ )), что означает, что конечная точка предыдущего шага будет сохранена. Следовательно:

c_{k}={\frac {{\frac {1}{2}}f(b_{k})a_{k}-f(a_{k})b_{k}}{{\frac {1}{2}}f(b_{k})-f(a_{k})}}

или

c_{k}={\frac {f(b_{k})a_{k}-{\frac {1}{2}}f(a_{k})b_{k}}{f(b_{k})-{\frac {1}{2}}f(a_{k})}},

уменьшение веса одного из конечных значений, чтобы заставить следующее $c k$ произойти на этой стороне функции. ^[10] Фактор ⁠1/2⁠ используемый выше выглядит произвольным, но он гарантирует сверхлинейную сходимость (асимптотически алгоритм будет выполнять два обычных шага после любого измененного шага и имеет порядок сходимости 1,442). Существуют и другие способы выбора перемасштабирования, которые дают еще лучшие сверхлинейные скорости сходимости. ^[11]

Вышеуказанная корректировка regula falsi некоторыми учеными называется алгоритмом Иллинойса . ^[10]^[12] Форд (1995) суммирует и анализирует этот и другие подобные суперлинейные варианты метода ложного положения. ^[11]

Алгоритм Андерсона–Бьёрка

Предположим, что в $k-й итерации интервал брекетинга равен [ak,bk]$ $и$ что $функциональное значение новой вычисленной оценки$ ck $имеет$ $тот$ же знак, что и $f$ $(bk) .$ В этом случае новый интервал брекетинга $[$ $ak$ $+1$ $,$ $bk$ $+1$ $]=[$ $ak,ck$ $]$ $и$ $левая$ $конечная$ точка сохранены. (Пока что это то же самое, что и обычный Regula Falsi и $алгоритм$ $Иллинойса$ $.$ $)$

$Но, в$ то время как алгоритм Иллинойса умножил бы $f (ak)$ на ⁠1/2⁠ , алгоритм Андерсона–Бьёрка умножает его на $m$ , где $m$ имеет одно из двух следующих значений: ^[13]

${\begin{aligned}m'&=1-{\frac {f(c_{k})}{f(b_{k})}},\\m&={\begin{cases}m'&{\text{if }}m'>0,\\{\frac {1}{2}}&{\text{otherwise.}}\end{cases}}\end{aligned}}$

Для простых корней метод Андерсона–Бьёрка на практике работает очень хорошо. ^[14]

Метод ИТП

При условии , и где — золотое сечение , на каждой итерации метод ИПТ вычисляет точку, следуя трем шагам: $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ $n_{1/2}\equiv \lceil (b_{0}-a_{0})/2\epsilon \rceil$ $n_{0}\in [0,\infty )$ $\phi$ ${\tfrac {1}{2}}(1+{\sqrt {5}})$ $j=0,1,2...$ $x_{\text{ITP}}$

[Шаг интерполяции] Вычислить точки бисекции и ложного правила: $x_{1/2}\equiv {\frac {a+b}{2}}$ и ; $x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}$
[Шаг усечения] Возмущаем оценку по направлению к центру: $x_{t}\equiv x_{f}+\sigma \delta$ где и ; $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ $\delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$
[Шаг проекции] Спроецируйте оценщик на интервал minmax: где . $x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}$

Значение функции в этой точке запрашивается, и интервал затем сокращается, чтобы заключить в скобки корень, сохраняя подынтервал со значениями функции противоположного знака на каждом конце. Эта трехшаговая процедура гарантирует, что минимальные свойства метода бисекции используются оценкой, а также сверхлинейная сходимость метода секущей. И, как наблюдается, превосходит как методы бисекции, так и методы, основанные на интерполяции, при гладких и негладких функциях. ^[15] $f(x_{\text{ITP}})$

Практические соображения

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

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

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

Затем программа может начать с метода Ньютона, и, если Ньютон не сходится, переключиться на regula falsi , возможно, в одной из его улучшенных версий, таких как версии Иллинойса или Андерсона–Бьёрка. Или, если даже это не сходится так же хорошо, как бисекция, переключиться на бисекцию, которая всегда сходится с полезной, если не впечатляющей, скоростью.

Когда изменение $y$ становится очень малым, а $x$ также меняется очень мало, то метод Ньютона, скорее всего, не столкнется с трудностями и будет сходиться. Так что при этих благоприятных условиях можно переключиться на метод Ньютона, если нужно, чтобы ошибка была очень маленькой, и нужна очень быстрая сходимость.

Пример: Рост камыша.

В главе 7 книги «Девять глав » задачу нахождения корня можно перевести на современный язык следующим образом:

Проблема избытка и дефицита №11:
Камыш вырос на 3 единицы в первый день. В конце каждого дня наблюдается рост растения на ⁠ 1 /2⁠ от роста предыдущего дня.
Клуб-раш вырос на 1 единицу в первый день. В конце каждого дня растение вырастало в 2 раза больше, чем в предыдущий день.
Найдите время [в долях дня] , когда камыш становится таким же высоким, как камыш.
Ответ: дней; высота — единиц. $(2+{\frac {6}{13}})$ $(4+{\frac {8}{10}}+{\frac {6}{130}})$
Объяснение:
Предположим, что это второй день. Камыш короче камыша на 1,5 единицы.
Предположим, что это день 3. Камыш выше камыша на 1,75 единицы. ∎

Чтобы понять это, мы смоделируем высоту растений в день $n$ ( $n$ = 1, 2, 3...) по геометрической прогрессии .

B(n)=\sum _{i=1}^{n}3\cdot {\frac {1}{2^{i-1}}}\quad

Камыш

C(n)=\sum _{i=1}^{n}1\cdot 2^{i-1}\quad

Клубная лихорадка

Для лучшей записи перепишем ряд высоты растений через $k$ и воспользуемся формулой суммы . $\ k=i-1~.$ $\ B(n),\ C(n)\$

\ B(n)=\sum _{k=0}^{n-1}3\cdot {\frac {1}{2^{k}}}=3\left({\frac {1-({\tfrac {1}{2}})^{n-1+1}}{1-{\tfrac {1}{2}}}}\right)=6\left(1-{\frac {1}{2^{n}}}\right)

\ C(n)=\sum _{k=0}^{n-1}2^{k}={\frac {~~1-2^{n}}{\ 1-2\ }}=2^{n}-1\

Теперь используйте regula falsi , чтобы найти корень $\ (C(n)-B(n))\$

\ F(n):=C(n)-B(n)={\frac {6}{2^{n}}}+2^{n}-7\

Установите и вычислите , что равно $-1,5$ («дефицит»). Установите и вычислите , что равно $1,75$ («избыток»). $\ x_{1}=2\$ $\ F(x_{1})=F(2)\$
$\ x_{2}=3\$ $\ F(x_{2})=F(3)\$

Расчетный корень (1-я итерация):

\ {\hat {x}}~=~{\frac {~x_{1}F(x_{2})-x_{2}F(x_{1})~}{F(x_{2})-F(x_{1})}}~=~{\frac {~2\times 1.75+3\times 1.5~}{1.75+1.5}}~\approx ~2.4615\

Пример кода

Этот пример программы, написанной на языке программирования C , является примером алгоритма Иллинойса. Чтобы найти положительное число $x,$ где $cos(x) = x 3$ , уравнение преобразуется в форму нахождения корня $f (x) = cos(x) - x 3 = 0$ .

#include <stdio.h> #include <math.h>  double f ( double x ) { return cos ( x ) - x * x * x ; } /* a,b: конечные точки интервала, в котором мы ищем  e: половина верхней границы относительной погрешности  m: максимальное число итераций */ double FalsiMethod ( double ( * f )( double ), double a , double b , double e , int m ) { double c , fc ; int n , side = 0 ; /* начальные значения в конечных точках интервала */ double fa = f ( a ); double fb = f ( b );                                    для ( n = 0 ; n < m ; n ++ ) { c = ( fa * b - fb * a ) / ( fa - fb ); если ( fabs ( b - a ) < e * fabs ( b + a )) перерыв ; fc = f ( c );                                    if ( fc * fb > 0 ) { /* fc и fb имеют одинаковый знак, копируем c в b */ b = c ; fb = fc ; if ( side == -1 ) fa /= 2 ; side = -1 ; } else if ( fa * fc > 0 ) { /* fc и fa имеют одинаковый знак, копируем c в a */ a = c ; fa = fc ; if ( side == + 1 ) fb /= 2 ; side = + 1 ; } else { /* fc * f_ очень маленькое (выглядит как ноль) */ break ; } } return c ; }                                                          int main ( void ) { printf ( "%0.15f \n " , FalsiMethod ( & f , 0 , 1 , 5E-15 , 100 )); return 0 ; }

После запуска этого кода окончательный ответ составит приблизительно 0,865474033101614.

Смотрите также

Метод ITP , вариация с гарантированной минимальной и сверхлинейной сходимостью
Метод Риддерса , еще один метод поиска корней, основанный на методе ложного положения.
Метод Брента

Ссылки

^ ab Katz, Victor J. (1998), История математики (2-е изд.), Addison Wesley Longman, стр. 15, ISBN 978-0-321-01618-8
^ abcd Смит, Д. Э. (1958) [1925], История математики , т. II, Дувр, стр. 437–441, ISBN 978-0-486-20430-7
^ Шабер, Жан-Люк, ред. (2012) [1999]. "3. Методы ложного положения". История алгоритмов: от Pebble до Microchip . Springer. стр. 86–91. ISBN 978-3-642-18192-4.
^ Нидхэм, Джозеф (1959). Математика и науки о небе и земле. Наука и цивилизация в Китае. Том 3. Cambridge University Press. С. 147–. ISBN 978-0-521-05801-8.
^ "Девять глав". www-groups.dcs.st-and.ac.uk . Получено 2019-02-16 .
^ Шен, Каншен; Кроссли, Джон Н.; Лун, Энтони Ва-Чунг (1999). Девять глав о математическом искусстве: Компаньон и комментарий. Oxford University Press. стр. 358. ISBN 978-7-03-006101-0.
^ ab Schwartz, RK (2004). Вопросы происхождения и развития Hisab al-Khata'ayn (Вычисление по двойной ложной позиции) . Восьмая североафриканская встреча по истории арабской математики. Радес, Тунис.Доступно онлайн по адресу: http://facstaff.uindy.edu/~oaks/Biblio/COMHISMA8paper.doc и "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2014-05-16 . Получено 2012-06-08 .{{cite web}}: CS1 maint: archived copy as title (link)
^ Генерал Траттато , том. I, Венеция, 1556, с. фол. 238, v, Regola Helcataym (vocabulo Arabo) che in nostra lingua vuol dire delle false Positioni
^ Конте, С.Д.; Бур, Карл де (1965). Элементарный численный анализ: алгоритмический подход (2-е изд.). МакГроу-Хилл. п. 40. ОКЛК 1088854304.
^ аб Далквист, Гермунд ; Бьорк, Оке (2003) [1974]. Численные методы. Дувр. стр. 231–232. ISBN 978-0486428079.
^ ab Ford, JA (1995), Улучшенные алгоритмы иллинойсского типа для численного решения нелинейных уравнений , Технический отчет, Издательство Эссекского университета, CiteSeerX 10.1.1.53.8676 , CSM-257
^ Доуэлл, М.; Джарратт, П. (1971). «Модифицированный метод regula falsi для вычисления корня уравнения». BIT . 11 (2): 168–174. doi :10.1007/BF01934364. S2CID 50473598.
^ Кинг, Ричард Ф. (октябрь 1983 г.). «Андерсон-Бьорк для линейных последовательностей». Математика вычислений . 41 (164): 591–596. doi :10.2307/2007695. JSTOR 2007695.
^ Галдино, Сержио (2011). «Семейство методов поиска корней regula falsi». Труды Всемирного конгресса по инжинирингу и технологиям 2011 года . 1. Получено 9 сентября 2016 г.
^ Оливейра, IFD; Такахаши, RHC (2020-12-06). «Улучшение средней производительности метода бисекции, сохраняющее оптимальность Minmax». ACM Transactions on Mathematical Software . 47 (1): 5:1–5:24. doi :10.1145/3423597. ISSN 0098-3500. S2CID 230586635.

Дальнейшее чтение

Burden, Richard L.; Faires, J. Douglas (2000). Числовой анализ (7-е изд.). Brooks/Cole. ISBN 0-534-38216-9.
Sigler, LE (2002). Liber Abaci Фибоначчи, Книга вычислений Леонардо Пизано . Springer-Verlag. ISBN 0-387-40737-5.
Робертс, AM (2020). «Математическая филология в трактате о двойной ложной позиции в арабской рукописи Колумбийского университета». Philological Encounters . 5 (3–4): 3–4. doi :10.1163/24519197-BJA10007. S2CID 229538951.(О ранее неопубликованном трактате о двойной ложной позиции в средневековой арабской рукописи.)