Target audience: Intermediate
Estimated reading time: 10'
This post presents two variants of the computation of the root of a function, implemented in Scala
The Newton-Raphson is a well-know technique to compute the root of a function, f(x) = 0 or the minimum/maximum of a function using its derivative f'(x) = 0.
The simplicity of the Newton-Raphson method, in term of concept as well as implementation makes it a very popular solution. We will look into two different implementation in Scala and conclude the post by evaluation the relative benefits and limitations of the Newton-Raphson.
The Newton-Raphson is a well-know technique to compute the root of a function, f(x) = 0 or the minimum/maximum of a function using its derivative f'(x) = 0.
The simplicity of the Newton-Raphson method, in term of concept as well as implementation makes it a very popular solution. We will look into two different implementation in Scala and conclude the post by evaluation the relative benefits and limitations of the Newton-Raphson.
First implementation
The construtor (lines 2 to 4) takes 3 arguments:
So far so good. However it is assumed that the function has a single root, or in the case of a maximum/minimum, its derivative has single root, at least in the vicinity of the initial data point. What about computing the root of a function which may have no or several root?
Let's look at the following function g and its derivate gg
The call to the Newton-Raphson method nr5 will diverge. In this particular case, the computation generates a Double.NaN, at each itertion.
There are several options to guarantee that the method will properly exit in the case no root exists. Let's look at one solution that leverages on the second derivative.
Let's dive into the computation of the root x of a function f. A function is defined by its Taylor series of derivatives as follow:
\[f(s)=\sum_{0}^{\infty }\frac{f^{(n)}(x)}{n!}(s-x)^{n}\] In case of the root f(s), the equation becomes
\[0=f(x)+f'(x)(x-s)+O((x-s)^{2}f"(s))\] resulting to
\[x_{n+1}=x_{n}- \frac{f(x_{n})}{f'(x_{n})}\]
\[f(s)=\sum_{0}^{\infty }\frac{f^{(n)}(x)}{n!}(s-x)^{n}\] In case of the root f(s), the equation becomes
\[0=f(x)+f'(x)(x-s)+O((x-s)^{2}f"(s))\] resulting to
\[x_{n+1}=x_{n}- \frac{f(x_{n})}{f'(x_{n})}\]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | final class NewtonRaphson( f: Double => Double, df: Double => Double, dff: Option[Double => Double] = None ) { final val EPS = 0.01 @scala.annotation.tailrec def root(z: Double): Double = dff.map(_dff => { val nextX = x - f(x) / df(x) if (Math.abs(nextX - x) < EPS) nextX else root(nextX) } } |
The construtor (lines 2 to 4) takes 3 arguments:
- Function which root is to be computed
- First order derivative
- Optional second order derivative that is not used in this first implementation
1 2 3 4 5 | val f = (x: Double) => Math.pow(x, 5.0) - 2.0*x val ff = (x: Double) => 5.0*Math.pow(x,4.0) -2.0 val nr1 = new NewtonRaphson(f, ff) val z1 = nr1.root(7.9) |
So far so good. However it is assumed that the function has a single root, or in the case of a maximum/minimum, its derivative has single root, at least in the vicinity of the initial data point. What about computing the root of a function which may have no or several root?
Let's look at the following function g and its derivate gg
1 2 3 4 | val g = (x: Double) => Math.exp(0.5 * x) val gg = (x: Double) => 0.5 * g(x) val nr3 = new NewtonRaphson(g, gg) |
The call to the Newton-Raphson method nr5 will diverge. In this particular case, the computation generates a Double.NaN, at each itertion.
There are several options to guarantee that the method will properly exit in the case no root exists. Let's look at one solution that leverages on the second derivative.
Second derivative to the rescue
Summary
We need to go back to basics: in its simplest form, the Newton-Raphson does not take into account the derivative of order higher than 1. The second order derivative, f" can be used as rough approximation of the error on the approximation of the root. The error san be evaluated at each iteration against a convergence criteria EPS.
\[\Delta \varepsilon = \varepsilon _{n+1}- \varepsilon _{n} \sim \frac{f'(x_{n})}{f"(x_{n})} < EPS\] \[x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}(1 + \Delta \varepsilon)\] The approximation of the error is also used to validate whether the algorithm converges toward a solution (root) or starts to diverge. Let's implement this variation of the Newton-Raphson using the second order derivative as a convergence criteria.
Once again, the computation of the root is implemented as an efficient tail recursion defined in the method nr2ndOrder (line 5)
The convergence criteria is implemented as follow:
\[\Delta \varepsilon = \varepsilon _{n+1}- \varepsilon _{n} \sim \frac{f'(x_{n})}{f"(x_{n})} < EPS\] \[x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}(1 + \Delta \varepsilon)\] The approximation of the error is also used to validate whether the algorithm converges toward a solution (root) or starts to diverge. Let's implement this variation of the Newton-Raphson using the second order derivative as a convergence criteria.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | @scala.annotation.tailrec def root(z: Double): Double = dff.map(_dff => { @scala.annotation.tailrec def nr2ndOrder(xe: (Double, Double)): (Double, Double) = { val x = xe._1 val eps = xe._2 val nextEps = Math.abs(df(x) / _dff(x)) val nextX = (x - f(x) *(1.0 + nextEps)/df(x)) // rules to exit recursion if (eps > 0.0 && nextEps >= eps) (-1.0, -1.0) else if (Math.abs(nextEps - eps) < EPS) (nextX, nextEps) else nr2ndOrder((nextX, nextEps)) } nr2ndOrder((z, 0.0))._1 }).getOrElse(DIVERGE) |
Once again, the computation of the root is implemented as an efficient tail recursion defined in the method nr2ndOrder (line 5)
The convergence criteria is implemented as follow:
- if error, eps increases, exit the recursion => Diverge (lines 13 and 22)
- if eps decreases with a value within the convergence criteria => Converged (line 15)
- if eps decreases with a value higher than the convergence criteria => Recurse (line 18)
Summary
Let's compare the convergence of the simplest Newton-Raphson method with the convergence its variant using the 2nd order derivative, using the function f defined in the first paragraph.
Clearly, the adaptive step size using the second order derivative speeds up the convergence toward the root of the function f. The selection of the appropriate method comes down to the trade-off between the overhead of the computation of the second derivative and the larger number of iterations or recursions required to find the root within a predefined convergence criteria.
Clearly, the adaptive step size using the second order derivative speeds up the convergence toward the root of the function f. The selection of the appropriate method comes down to the trade-off between the overhead of the computation of the second derivative and the larger number of iterations or recursions required to find the root within a predefined convergence criteria.
References
- Programming in Scala 2nd Edition M. Odersky, L. Spoon, B. Venners - Artima - 2012
- The Newton-Raphson method
Great Article I love to read your articles because your writing style is too good, its is very very helpful for all of us and I never get bored while reading your article because it becomes more and more interesting from the starting lines until the end. So Thank you for sharing a COOL Meaningful stuff with us Keep it up..!
ReplyDeleteSAP training in Chennai
The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. machine learning projects for final year In case you will succeed, you have to begin building machine learning projects in the near future.
DeleteProjects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.
Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.
The Nodejs Training Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training
ReplyDeleteAll are saying the same thing repeatedly, but in your blog I had a chance to get some useful and unique information, I love your writing style very much, I would like to suggest your blog in my dude circle, so keep on updates.
SAP training in Chennai
Wow amazing i saw the article with execution models you had posted. It was such informative. Really its a wonderful article. Thank you for sharing and please keep update like this type of article because i want to learn more relevant to this topic.
ReplyDeleteSEO Company in Chennai
ReplyDeleteشركة غسيل خزانات بالمدينة المنورة شركة غسيل خزانات بالمدينة المنورة
افضل شركة تنظيف منازل بالمدينة المنورة شركة تنظيف منازل بالمدينة المنورة
Невероятно познавательныеи к тому же поразительно точнейшие онлайн гадания для познания нашего будущего, это непременно то, что увидит вас на нашем сайте. Правдивое гадание на картах, на будущее является действенным быстрым и простым способом для получения важных информаций из энерегетического поля земли.
ReplyDeleteНевероятно потрясающие и поразительно точнейшие онлайн гадания для предречения вашего дня грядущего, это именно то, что вы найдете на портале гаданий. Точное гадание на картах таро, на будущее является самым доступным и легким вариантом для извлечения нужных знаний из эмпирического поля планеты Земля.
ReplyDeleteЛюбые методы предсказания будущего обозначаются как мистические учения. Всякий характер ворожбы исключителен и необходим для разных целей. Гадание на картах на женщину и точность предсказаний будущего напрямую зависит от умения человека. Всякий хочет предугадать свое будущее и представляет определенные средства гадания максимально достоверными.
ReplyDeleteБольшое число игр изготавливается ежегодно. В наибольшей степени верным путем приобрести ожидаемую игру представляется бесплатно скачать взлом игры про дрифт. Быть знатоком в элементах популярных игрушек не так легко по вине нереального их объема. Загружая игры с Torrent вы получаете максимальный уровень защиты. Обманщики могут использовать глупость заказчиков и распространять вирусы. Загрузка Torrent является обыкновенной процедурой, понятной даже для начинающих юзеров.
ReplyDeleteThis article is very useful. Thank you very much. https://youtube-to-mp3-converter.com/ - and here is a link to my site, which I launched recently. Youtube to mp3 service allows you to download music to your iPhone for free in less than a minute.
ReplyDeleteНа портале mp3smak.ru имеется все что хотите – скачать зарубежную музыку бесплатно. Какую угодно музыку, показанную на нашей платформе, разрешено загрузить вполне без оплаты. Найдите новейшую музыку для поездки на дачу или увлекательной пьянки. Непосредственно свежаки нынешнего сезона в лучшем формате. mp3smak.ru – популярнейший исключительный музыкальный портал, какой поможет найти подходящее в короткое время. На земле есть огромное число mp3 на любой вкус.
ReplyDeleteКомплекс действий, направленных на предвидение жизненного пути, именуют гадание. Гадание ленорман - это проверенный вариант поворожить с применением каких-либо объектов и приемов. Магические силы и различные обстановки ворожения наукой не описаны, однако многие люди верят в это.
ReplyDeleteМногочисленные коммунальные компании сталкиваются с трудностью поставок всякого рода контейнеров. Предприятие СнабТоп.ру посодействует потребителям купить здесь купить уличные скамейки из дерева по особо конкурентноспособной цене на выгодных условиях. Стройинвентарь для ЖКХ по крайне выгодным ценам.
ReplyDeleteКерамику возможно использовать в залах организаций общественного питания, в школах и детских садиках. Нетоксичный материал, совершенно безопасен для людей. Плитку плитка orbit dual gres делают в основном из природных материалов.
ReplyDeleteВоспользовавшись порталом займ через систему контакт без отказов, вы можете самостоятельно просмотреть необходимые проценты по кредиту. Возьмите денежные средства на карту на любые цели. Именно ответственные фирмы реализуют свои действия на сайте «СкороДеньги».
ReplyDeleteПройдите регистрацию на главной странице и получите полезные очки в своей учетке. Необходимо помнить, что проект казино х отзывы реальные предлагает всем посетителям специальные вознаграждения. Бонусный счет позволяет сгрести немало денежных средств.
ReplyDeleteСервисная служба круглосуточно придет на помощь и мгновенно решит максимально тяжелую задачу. Имейте в виду, что казино онлайн казино х рабочее зеркало ни при каких условиях не потребует деньги за выполнение процесса верификации посетителей. Просмотреть истинность игрового сервиса реально на официальной странице casino-x-oficialniy-sayt.com.
ReplyDeleteИграться с друзьями значительно веселее, чем сам по себе на хате. Посещая интерактивный клуб, вы можете окунуться в невероятные приключения. Собственно на странице mr bit casino официальный зеркало пользователи легко разыщут любимую виртуальную игрушку для отдыха.
ReplyDeleteВ игровом доме Frank-Casino гемблер сможет очень просто увидеть раздел регистрации на заглавной странице портала. Авторизация на сайте игорный дом FrankCasinoClub не занимает много времени. Осуществите верный выбор – промокод франк казино 2020 твой вариант на победу! Присоединяйтесь к игровой площадке и берите отличные вознаграждения в своей учетной записи.
ReplyDeleteНужно уделить отдельное внимание подбору оптимально подходящего для вас ресурса. Именно на сайте joycasino мобильная версия россия вы сможете получить большие бабки. В мире реализованы сотни веб-казино на реальные денежки.
ReplyDeleteКерамику плитка cerrad loft спб поставляют в огромном количестве, и любая фирма хочет выпустить особый невообразимый проект. Разнообразие тонов и размеров. Ценовой диапазон покрытия также расходится.
ReplyDeleteСаша Спилберг слитые откровенные фото без цензуры 18+
ReplyDeletebape hoodie
ReplyDeleteyeezy boost 350 v2
supreme
supreme clothing
golden goose
golden goose sneakers
yeezy boost 350 v2
curry 8 shoes
moncler coat
moncler