В математике , то Регула falsi , метод ложного положения или ложного метода положения является очень старый метод для решения уравнения с одним неизвестным, что, в модифицированном виде, все еще используется. Проще говоря, этот метод представляет собой метод проб и ошибок, заключающийся в использовании тестовых («ложных») значений переменной и последующей корректировке тестового значения в соответствии с результатом. Иногда это также называют «угадать и проверить». Версии этого метода предшествовали появлению алгебры и использованию уравнений .
В качестве примера рассмотрим задачу 26 из папируса Райнда , которая требует решения (записанного в современных обозначениях) уравнения x + x / 4 = 15 . Это решается ложной позицией. [1] Сначала предположим, что x = 4, чтобы получить слева 4 + 4/4 = 5 . Это предположение является хорошим выбором, поскольку оно дает целочисленное значение. Однако число 4 не является решением исходного уравнения, поскольку дает значение, которое в три раза меньше. Для компенсации умножьте x (в настоящее время установлено на 4) на 3 и снова замените, чтобы получить 12 + 12/4 = 15 , проверяя, что решение равно x = 12 .
Современные версии метода используют систематические способы выбора новых тестовых значений и связаны с вопросами о том, может ли быть получено приближение к решению, и, если это возможно, как быстро можно найти приближение.
Два исторических типа
Исторически можно выделить два основных типа метода ложной позиции: простая ложная позиция и двойная ложная позиция .
Простая ложная позиция направлена на решение задач, связанных с прямой пропорциональностью. Такие задачи можно записать алгебраически в виде: определить x такое, что
если известны a и b . Метод начинается с использования тестового входного значения x ' и нахождения соответствующего выходного значения b ' умножением: ax '= b ' . Затем правильный ответ находится путем пропорциональной регулировки, x =б/ б ' х ' .
Двойная ложная позиция направлена на решение более сложных задач, которые алгебраически можно записать в виде: определить x такое, что
если известно, что
Двойное ложное положение математически эквивалентно линейной интерполяции . Используя пару тестовых входов и соответствующую пару выходов, результат этого алгоритма определяется как, [2]
будет запоминаться и выполняться наизусть. В самом деле, правило, данное Робертом Рекордом в его «Земле искусств» (ок. 1542 г.), таково: [2]
Гессе на этой работе, как оказалось, ведет.
По правде говоря, вы можете продолжить.
И первое дело по вопросу,
Хотя никакой правды в этом нет.
Такой фальшход такой хороший землянин,
Эта истина скоро будет утрачена.
От многих бате до многих мес,
От к немногим возьмите и к немногим.
С большим количеством ягод, чтобы снова меньше,
К малому добавляем к манье равнине.
В кроссвейнах размножаются противоположные роды,
Все верно ложным путем для поиска.
Для аффинной линейной функции ,
double false position дает точное решение, а для нелинейной функции f дает приближение, которое может быть последовательно улучшено итерацией .
История
Простая техника ложного положения встречается в клинописных табличках из древней вавилонской математики и в папирусах из древнеегипетской математики . [3] [1]
Двойная ложная позиция возникла в поздней античности как чисто арифметический алгоритм. В древнем китайском математическом тексте под названием «Девять глав математического искусства» (九章 算術) [4], датируемом периодом с 200 г. до н.э. по 100 г. н.э., большая часть главы 7 была посвящена алгоритму. Там процедура была обоснована конкретными арифметическими аргументами, а затем творчески применена к широкому кругу задач-сюжетов, в том числе к той, которая связана с тем, что мы бы назвали секущими линиями на коническом сечении . Более типичный пример - это проблема «совместной покупки»: [5]
Теперь товар покупается совместно; каждый вносит 8 [монет], превышение - 3; каждый вносит 7, дефицит - 4. Скажите: количество людей, цена товара, что за каждый? Ответ: 7 человек, цена товара 53. [6]
Между 9-м и 10-м веками египетский математик Абу Камил написал ныне утерянный трактат об использовании двойного ложного положения, известный как Книга двух ошибок ( Китаб аль-ханадайн ). Самая старая из сохранившихся письменных работ о двойной ложной позиции с Ближнего Востока - это Куста ибн Лука (10 век), арабский математик из Баальбека , Ливан . Он обосновал эту технику формальным геометрическим доказательством в евклидовом стиле . В традициях средневековой мусульманской математики двойная ложная позиция была известна как хисаб аль-хатанайн («расчет двумя ошибками»). Он веками использовался для решения практических задач, таких как коммерческие и юридические вопросы (раздел поместья в соответствии с правилами наследования Корана ), а также чисто рекреационных проблем. Алгоритм часто запоминался с помощью мнемоники , такой как стих, приписываемый Ибн аль-Ясамину, и диаграммы баланса, объясненные аль-Хассаром и Ибн аль-Банной , все трое были математиками марокканского происхождения. [7]
Леонардо Пизанский ( Фибоначчи ) посвятил 13-ю главу своей книги Liber Abaci (1202 г. н.э.) объяснению и демонстрации использования двойного ложного положения, назвав метод регулис эльчатайн в честь метода аль-ханадайн, который он узнал из арабских источников. [7] В 1494 году Пачоли использовал термин el cataym в своей книге Summa de arithmetica , вероятно, позаимствовав термин у Фибоначчи. Другие европейские писатели последовали примеру Пачоли и иногда переводили его на латынь или другие языки. Например, Тарталья переводит латинизированную версию термина Пачоли на народное «ложное положение» в 1556 году. [8] Термин Пачоли почти исчез в европейских работах 16-го века, и техника получила различные названия, такие как «Правило ложного» ». Правило положения »и« Правило ложного положения ». 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 ) .
Существует множество алгоритмов поиска корня, которые можно использовать для получения приближений к такому корню. Одним из наиболее распространенных является метод Ньютона , но он может не найти корень при определенных обстоятельствах , и это может быть вычислительно дорогостоящей , так как требует вычисления функции по производной . Необходимы другие методы, и один общий класс методов - это методы двухточечной скобки . Эти методы продолжаются путем создания последовательности сокращающихся интервалов [ a k , b k ] на k- м шаге, так что ( a k , b k ) содержит корень f .
Методы двухточечного брекетинга
Эти методы начинаются с двух значений x , первоначально найденных методом проб и ошибок, при которых f ( x ) имеет противоположные знаки. В предположении непрерывности корень f гарантированно лежит между этими двумя значениями, то есть эти значения «заключают в скобки» корень. Затем выбирается точка строго между этими двумя значениями и используется для создания меньшего интервала, который по-прежнему ограничивает корень. Если c - выбранная точка, то меньший интервал идет от c до конечной точки, где f ( x ) имеет знак, противоположный знаку f ( c ) . В маловероятном случае, когда f ( c ) = 0 , корень найден и алгоритм останавливается. В противном случае процедура повторяется столько раз, сколько необходимо, чтобы получить приближение к корню с любой желаемой точностью.
Точку, выбранную в любом текущем интервале, можно рассматривать как оценку решения. Различные варианты этого метода включают разные способы вычисления этой оценки решения.
Сохранение брекетинга и обеспечение того, чтобы оценки решения лежали внутри интервалов брекетинга, гарантирует, что оценки решения будут сходиться к решению, а это гарантия недоступна с другими методами поиска корня, такими как метод Ньютона или метод секущей .
Простейший вариант, называемый методом деления пополам , вычисляет оценку решения как середину интервала заключения в скобки. То есть, если на шаге k текущий интервал брекетинга равен [ a k , b k ] , то новая оценка решения c k получается следующим образом:
Это гарантирует, что c k находится между a k и b k , тем самым гарантируя сходимость к решению.
Поскольку длина интервала брекетинга уменьшается вдвое на каждом шаге, ошибка метода деления пополам в среднем уменьшается вдвое с каждой итерацией. Следовательно, каждые 3 итерации метод увеличивает точность примерно в 2–3 раза , то есть примерно до десятичного разряда.
Метод regula falsi (ложное положение)
Скорость сходимости метода деления пополам можно было бы улучшить, используя другую оценку решения.
Регул falsi метод вычисляет новую оценку решения в качестве й -intercept части отрезки , соединяющей концы функции на текущем интервале брекетинга. По сути, корень аппроксимируется путем замены фактической функции отрезком линии на интервале брекетинга, а затем с использованием классической формулы двойного ложного положения на этом отрезке линии. [9]
Точнее, предположим, что на k -й итерации интервал скобок равен ( a k , b k ) . Постройте линию через точки ( a k , f ( a k )) и ( b k , f ( b k )) , как показано на рисунке. Эта линия является секущей или хордой графика функции f . В форме точечного уклона его уравнение имеет вид
Теперь выберите c k как точку пересечения с x этой линии, то есть значение x, для которого y = 0 , и подставьте эти значения, чтобы получить
Решение этого уравнения относительно c 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 ") ). Как следствие, линейная аппроксимация to f ( x ) , который используется для выбора ложной позиции, не улучшается настолько быстро, насколько это возможно.
Одним из примеров этого явления является функция
на исходной скобке [−1,1]. Левый конец, −1, никогда не заменяется (сначала он не изменяется, а после первых трех итераций f " отрицателен на интервале), и, таким образом, ширина скобки никогда не опускается ниже 1. Следовательно, правая конечная точка приближается к 0 с линейной скоростью (количество точных цифр растет линейно, со скоростью сходимости 2/3). [ Необходима ссылка ]
Для прерывных функций можно ожидать, что этот метод найдет только точку, в которой функция меняет знак (например, при x = 0 для 1 / x или функции знака ). Помимо изменения знака, метод также может сходиться к точке, где предел функции равен нулю, даже если функция не определена (или имеет другое значение) в этой точке (например, при x = 0 для функция, заданная формулой f ( x ) = abs ( x ) - x 2, когда x ≠ 0, и f (0) = 5 , начиная с интервала [-0,5, 3,0]). Математически возможно, что с разрывными функциями метод не сойдется к нулевому пределу или изменению знака, но на практике это не проблема, так как потребовалась бы бесконечная последовательность совпадений для обеих конечных точек, чтобы застрять и сходиться к разрывам, где знак не меняется, например при x = ± 1 в
Метод бисекции устраняет эту гипотетическую проблему сходимости.
Улучшения в regula falsi
Хотя regula falsi всегда сходится, обычно значительно быстрее, чем деление пополам, бывают ситуации, которые могут замедлить его схождение - иногда до недопустимой степени. Эта проблема не является уникальной для regula falsi : кроме деления пополам, все численные методы решения уравнений могут иметь проблему медленной сходимости или отсутствия сходимости при некоторых условиях. Иногда метод Ньютона и метод секущей расходятся, а не сходятся - и часто это происходит в тех же условиях, которые замедляют сходимость regula falsi .
Но, хотя regula falsi является одним из лучших методов, и даже в его исходной неулучшенной версии часто оказывается лучшим выбором; например, когда Ньютон не используется, потому что производная требует чрезмерно много времени для вычисления, или когда Ньютон и Последовательные замены не смогли сойтись.
Режим отказа Regula falsi легко обнаружить: одна и та же конечная точка сохраняется дважды подряд. Проблему легко решить, выбрав вместо этого модифицированную ложную позицию, выбранную во избежание замедлений из-за этих относительно необычных неблагоприятных ситуаций. Было предложено несколько таких улучшений для regula falsi ; два из них, алгоритм Иллинойса и алгоритм Андерсона – Бьорка, описаны ниже.
Алгоритм Иллинойса
Алгоритм Иллинойса уменьшает вдвое значение y сохраненной конечной точки при следующем вычислении оценки, когда новое значение y (то есть f ( c k )) имеет тот же знак, что и предыдущее ( f ( c k - 1 ) ), что означает, что конечная точка предыдущего шага будет сохранена. Следовательно:
или же
уменьшение веса одного из значений конечной точки, чтобы заставить следующее c k произойти на этой стороне функции. [10] Коэффициент ½, использованный выше, выглядит произвольно, но он гарантирует суперлинейную сходимость (асимптотически алгоритм будет выполнять два обычных шага после любого модифицированного шага и имеет порядок сходимости 1.442). Есть и другие способы выбора масштабирования, которые обеспечивают еще лучшую скорость сверхлинейной сходимости. [11]
Вышеупомянутая поправка к regula falsi некоторыми учеными называется алгоритмом Иллинойса . [10] [12] Форд (1995) обобщает и анализирует этот и другие подобные суперлинейные варианты метода ложного положения. [11]
Алгоритм Андерсона – Бьорка
Предположим, что на k -й итерации интервал заключения в скобки равен [ a k , b k ] и что функциональное значение новой вычисленной оценки c k имеет тот же знак, что и f ( b k ) . В этом случае новый интервал брекетинга [ a k + 1 , b k + 1 ] = [ a k , c k ] и левая конечная точка была сохранена. (Пока что это то же самое, что и обычный алгоритм Регулы Фальси и алгоритм Иллинойса.)
Но, в то время как алгоритм Иллинойса умножил бы f ( a k ) на 1/2, Алгоритм Андерсона – Бьорка умножает его на m , где m имеет одно из двух следующих значений:
- если это значение m положительно,
в противном случае пусть .
Для простых корней Андерсон-Бьорк очень хорошо работает на практике. [13] [14]
Метод ИТП
Дано , а также где золотой паек , в каждой итерации метод ITP вычисляет точку следующие три шага:
- [Шаг интерполяции] Вычислите точку пополам и точки ложного смещения: а также ;
- [Шаг усечения] Переместите оценщик к центру: где а также ;
- [Шаг проекции] Спроецируйте оценку на минимальный интервал: где .
Значение функции в этой точке выполняется запрос, а затем интервал сокращается до скобки корня, сохраняя подинтервал со значениями функций противоположного знака на каждом конце. Эта трехшаговая процедура гарантирует, что при оценке используются свойства minmax метода деления пополам, а также суперлинейная сходимость метода секущей. И, как наблюдается, превосходит методы, основанные на делении пополам и интерполяции, при гладких и негладких функциях. [15]
Практические соображения
При решении одного или нескольких уравнений с помощью компьютера метод деления пополам является адекватным выбором. Хотя деление пополам не так быстро, как другие методы - когда они в лучшем виде и не имеют проблем, - тем не менее, деление пополам гарантированно сходится с полезной скоростью, примерно вдвое уменьшая ошибку с каждой итерацией - получая примерно десятичную дробь. место точности через каждые 3 итерации.
Для ручного расчета с помощью калькулятора обычно используются более быстрые методы, и они обычно, но не всегда, сходятся быстрее, чем деление пополам. Но компьютер, даже используя деление пополам, решит уравнение с желаемой точностью так быстро, что нет необходимости пытаться сэкономить время, используя менее надежный метод - и каждый метод менее надежен, чем деление пополам.
Исключение было бы, если бы компьютерной программе приходилось решать уравнения очень много раз во время своего выполнения. Тогда время, сэкономленное более быстрыми методами, может быть значительным.
Затем программа могла бы начать с метода Ньютона и, если метод Ньютона не сходится, переключиться на regula falsi , возможно, в одной из его улучшенных версий, таких как версии Иллинойса или Андерсона – Бьорка. Или, если даже это не сходится так хорошо, как деление пополам, переключитесь на деление пополам, которое всегда сходится с полезной, если не впечатляющей, скоростью.
Когда изменение y стало очень небольшим, а x также меняется очень мало, тогда метод Ньютона, скорее всего, не столкнется с проблемами и будет сходиться. Таким образом, при этих благоприятных условиях можно было бы переключиться на метод Ньютона, если бы вы хотели, чтобы ошибка была очень маленькой и хотелось очень быстрой сходимости.
Пример кода
Этот пример программы, написанный на языке программирования C , является примером алгоритма Иллинойса. Чтобы найти положительное число x, где cos ( x ) = x 3 , уравнение преобразуется в форму для поиска корней f ( x ) = cos ( x ) - x 3 = 0 .
#include #include двойной f ( двойной x ) { return cos ( x ) - x * x * x ; } / * s, t: конечные точки интервала, в котором мы ищем e: половина верхней границы относительной ошибки m: максимальное количество итераций * / double FalsiMethod ( double s , double t , double e , int m ) { double r , fr ; int n , сторона = 0 ; / * начальные значения в конечных точках интервала * / double fs = f ( s ); двойной ft = f ( t ); for ( n = 0 ; n < m ; n ++ ) { r = ( фс * т - фут * с ) / ( фс - фут ); если ( fabs ( t - s ) < e * fabs ( t + s )) перерыв ; fr = f ( r ); если ( fr * ft > 0 ) { / * fr и ft имеют одинаковый знак, скопируйте r в t * / t = r ; ft = fr ; если ( сторона == -1 ) fs / = 2 ; сторона = -1 ; } else if ( fs * fr > 0 ) { / * fr и fs имеют одинаковый знак, скопируйте r в s * / s = r ; fs = fr ; если ( сторона == + 1 ) ft / = 2 ; сторона = + 1 ; } else { / * fr * f_ очень маленький (выглядит как ноль) * / break ; } } return r ; }int main ( void ) { printf ( "% 0.15f \ n " , FalsiMethod ( 0 , 1 , 5E-15 , 100 )); возврат 0 ; }
После запуска этого кода окончательный ответ будет примерно 0.865474033101614.
Смотрите также
- Метод ITP , вариант с гарантированным minmax и сверхлинейной сходимостью
- Метод Риддерса , еще один метод поиска корней, основанный на методе ложного положения.
- Метод Брента
Рекомендации
- ^ a b Кац, Виктор Дж. (1998), История математики (2-е изд.), Аддисон Уэсли Лонгман, стр. 15 , ISBN 978-0-321-01618-8
- ^ а б в г Смит, Д.Е. (1958) [1925], История математики , II , Довер, стр. 437–441, ISBN 978-0-486-20430-7
- ^ Шабер, Жан-Люк, изд. (2012) [1999]. «3. Методы ложной позиции» . История алгоритмов: от гальки до микрочипа . Springer. С. 86–91. ISBN 978-3-642-18192-4.
- ^ Нидхэм, Джозеф (1959). Математика и науки о небе и Земле . Наука и цивилизация в Китае. 3 . Издательство Кембриджского университета. С. 147–. ISBN 978-0-521-05801-8.
- ^ «Девять глав» . www-groups.dcs.st-and.ac.uk . Проверено 16 февраля 2019 .
- ^ Шен, Каншен; Кроссли, Джон Н .; Лун, Энтони Ва-Чунг (1999). Девять глав по математическому искусству: компаньоны и комментарии . Издательство Оксфордского университета. п. 358. ISBN 978-7-03-006101-0.
- ^ а б Шварц, РК (2004). Проблемы происхождения и развития Хисаб аль-Хатаайн (Расчет двойным ложным положением) . Восьмое Североафриканское совещание по истории арабской математики. Радес, Тунис.Доступно в Интернете по адресу: http://facstaff.uindy.edu/~oaks/Biblio/COMHISMA8paper.doc и «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 16 мая 2014 года . Проверено 8 июня 2012 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ Генерал Траттато , I , Венеция, 1556 г., стр. fol. 238, v,
Regola Helcataym (dictionary Arabo) che in nostra lingua vuol dire delle false Positioni
- ^ Конте, SD; Бур, Карл де (1965). Элементарный численный анализ: алгоритмический подход (2-е изд.). Макгроу-Хилл. п. 40. OCLC 1088854304 .
- ^ а б Дальквист, Гермунд ; Бьорк, Оке (2003) [1974]. Численные методы . Дувр. С. 231–232. ISBN 978-0486428079.
- ^ а б Ford, JA (1995), Улучшенные алгоритмы типа Иллинойса для численного решения нелинейных уравнений , Технический отчет, University of Essex Press, CiteSeerX 10.1.1.53.8676 , CSM-257
- ^ Dowell, M .; Джарратт П. (1971). «Модифицированный метод regula falsi для вычисления корня уравнения». БИТ . 11 (2): 168–174. DOI : 10.1007 / BF01934364 . S2CID 50473598 .
- ^ Галдино, Сержио (2011). «Семейство методов поиска корней regula falsi» . Труды 2011 Всемирного конгресса по технике и технологии . 1 . Проверено 9 сентября +2016 .
- ^ Галдино, Сержио (2011). «Семейство методов поиска корней regula falsi» . Проверено 11 июля 2017 года . Цитировать журнал требует
|journal=
( помощь ) - ^ Оливейра, IFD; Такахаши, RHC (06.12.2020). «Улучшение средней производительности метода деления пополам с сохранением минимальной оптимальности» . Транзакции ACM на математическом программном обеспечении . 47 (1): 5: 1–5: 24. DOI : 10.1145 / 3423597 . ISSN 0098-3500 .
дальнейшее чтение
- Бэрден, Ричард Л .; Фэрс, Дж. Дуглас (2000). Численный анализ (7-е изд.). Брукс / Коул. ISBN 0-534-38216-9.
- Сиглер, Л. Е. (2002). Liber Abaci Фибоначчи, Книга расчетов Леонардо Пизано . Springer-Verlag. ISBN 0-387-40737-5.
- Робертс, AM (2020). «Математическая филология в трактате о двойной ложной позиции в арабской рукописи Колумбийского университета» . Филологические встречи . 5 (3–4): 3–4. DOI : 10.1163 / 24519197-BJA10007 . (О ранее неопубликованном трактате о двойной ложной позиции в средневековой арабской рукописи.)