Miller's recurrence algorithm

Numerical analysis | Algorithms

Miller's recurrence algorithm is a procedure for calculating a rapidly decreasing solution of a linear recurrence relation developed by J. C. P. Miller. It was originally developed to compute tables of the modified Bessel function but also applies to Bessel functions of the first kind and has other applications such as computation of the coefficients of Chebyshev expansions of other special functions. Many families of special functions satisfy a recurrence relation that relates the values of the functions of different orders with common argument . The modified Bessel functions of the first kind satisfy the recurrence relation . However, the modified Bessel functions of the second kind also satisfy the same recurrence relation . The first solution decreases rapidly with . The second solution increases rapidly with . Miller's algorithm provides a numerically stable procedure to obtain the decreasing solution. To compute the terms of a recurrence through according to Miller's algorithm, one first chooses a value much larger than and computes a trial solution taking initial condition to an arbitrary non-zero value (such as 1) and taking and later terms to be zero. Then the recurrence relation is used to successively compute trial values for , down to . Noting that a second sequence obtained from the trial sequence by multiplication by a constant normalizing factor will still satisfy the same recurrence relation, one can then apply a separate normalizing relationship to determine the normalizing factor that yields the actual solution. In the example of the modified Bessel functions, a suitable normalizing relation is a summation involving the even terms of the recurrence: where the infinite summation becomes finite due to the approximation that and later terms are zero. Finally, it is confirmed that the approximation error of the procedure is acceptable by repeating the procedure with a second choice of larger than the initial choice and confirming that the second set of results for through agree within the first set within the desired tolerance. Note that to obtain this agreement, the value of must be large enough such that the term is small compared to the desired tolerance. In contrast to Miller's algorithm, attempts to apply the recurrence relation in the forward direction starting from known values of and obtained by other methods will fail as rounding errors introduce components of the rapidly increasing solution. Olver and Gautschi analyses the error propagation of the algorithm in detail. For Bessel functions of the first kind, the equivalent recurrence relation and normalizing relationship are: . The algorithm is particularly efficient in applications that require the values of the Bessel functions for all orders for each value of compared to direct independent computations of separate functions. (Wikipedia).

Discrete Math - 2.4.2 Recurrence Relations

What is a recurrence relation, and how can we write it as a closed function? Textbook: Rosen, Discrete Mathematics and Its Applications, 7e Playlist: https://www.youtube.com/playlist?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz

From playlist Discrete Math I (Entire Course)

Find the limit of a recurrence, and a challenge problem to find the formula for the sequence

#shorts #mathonshorts With the given recurrence, we want to find the limit of the sequence. The trick is to identify the recurrence as the one in Newton's method for root finding. A challenge problem to find the formula for the sequence. Please leave your answers in the comment.

From playlist "Smarter In-A-Minute" Math on Shorts

Sequences: Introduction to Solving Recurrence Relations

This video introduces solving recurrence relations by the methods of inspection, telescoping, and characteristic root technique. mathispower4u.com

From playlist Sequences (Discrete Math)

First Order Linear Recurrence Relations

From playlist N. Proofs and Recurrence Relations

Evaluating Recurrence Relations (1 of 4: When do you apply Recurrence Relations?)

More resources available at www.misterwootube.com

From playlist Further Integration

Second Order Recurrence Formula (1 of 3: Prologue - considering the old course)

More resources available at www.misterwootube.com

From playlist Further Proof by Mathematical Induction

Global symmetry from local information: The Graph Isomorphism Problem – László Babai – ICM2018

Combinatorics | Mathematical Aspects of Computer Science Invited Lecture 13.4 | 14.5 Global symmetry from local information: The Graph Isomorphism Problem László Babai Abstract: Graph Isomorphism (GI) is one of a small number of natural algorithmic problems with unsettled complexity stat

From playlist Combinatorics

Mioara Joldes: Validated symbolic-numerci algorithms and practical applications in aerospace

In various fields, ranging from aerospace engineering or robotics to computer-assisted mathematical proofs, fast and precise computations are essential. Validated (sometimes called rigorous as well) computing is a relatively recent field, developed in the last 20 years, which uses numerica

From playlist Probability and Statistics

Iteration

From playlist Numerical Methods

Gregory Miermont - Un panorama des limites d'échelles de cartes aléatoires

From playlist Des mathématiciens primés par l'Académie des Sciences 2017

Discrete Math II - 8.2.1 Solving First-Order Linear Homogeneous Recurrence Relations

We take another look at First-Order Linear Homogeneous Recurrence relations (and what exactly all of that means). We took our first look in section 8.1 by using back substitution and iteration. In this video we look at one example using both methods, then dive into further detail on how to

From playlist Discrete Math II/Combinatorics (entire course)

AI DEBATE : Yoshua Bengio | Gary Marcus

Yoshua Bengio and Gary Marcus on the best way forward for AI Moderated by Vincent Boucher ORIGINAL LIVE STREAMING | Monday, 23 December 2019 from 6:30 PM to 8:30 PM (EST) at Mila: https://www.facebook.com/MontrealAI/videos/498403850881660/ Transcript of the AI Debate: https://medium.com/

From playlist AI talks

25. Interpretability

MIT 6.S897 Machine Learning for Healthcare, Spring 2019 Instructor: Peter Szolovits View the complete course: https://ocw.mit.edu/6-S897S19 YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP60B0PQXVQyGNdCyCTDU1Q5j Prof. Szolovits discusses interpretability because modern

From playlist MIT 6.S897 Machine Learning for Healthcare, Spring 2019

RECURRENCE RELATIONS using GENERATING FUNCTIONS - DISCRETE MATHEMATICS

Learn how to solve recurrence relations with generating functions. Visit our website: http://bit.ly/1zBPlvm Subscribe on YouTube: http://bit.ly/1vWiRxW *--Playlists--* Discrete Mathematics 1: https://www.youtube.com/playlist?list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz Discrete Mathematics 2:

From playlist Discrete Math 2

Reinforcement Learning 9: A Brief Tour of Deep RL Agents

Volodymyr Mnih, Research Scientist, discusses deep RL agents as part of the Advanced Deep Learning & Reinforcement Learning Lectures.

From playlist DeepMind x UCL | Reinforcement Learning Course 2018

Lecture 19.7 - Recurrence Relations

This is Lecture 19.7 of the CSE373 (Analysis of Algorithms) taught by Professor Steven Skiena [http://www.cs.sunysb.edu/~skiena/] at Stony Brook University in 1997. The lecture slides are available at: http://www.cs.sunysb.edu/~algorith/video-lectures/1997/lecture3.pdf

From playlist CSE373 - Analysis of Algorithms - 1997 SBU

Lecture 19 - Edit Distance I

This is Lecture 19 of the CSE373 (Analysis of Algorithms) course taught by Professor Steven Skiena [http://www3.cs.stonybrook.edu/~skiena/] at Stony Brook University in 2016. The lecture slides are available at: https://www.cs.stonybrook.edu/~skiena/373/newlectures/lecture17.pdf More inf

From playlist CSE373 - Analysis of Algorithms 2016 SBU

11th Annual Yale NEA-BPD Conference: Overview of BPD

Dr. Ansell is an Assistant Professor in Psychiatry at Yale University and a member of the Yale Stress Center. She graduated with a PhD in clinical psychology from the Pennsylvania State University in 2005 and completed a postdoctoral fellowship at Yale working on the NIMH funded Collaborat

From playlist 11th Annual Yale NEA-BPD Conference: Meeting the Needs of Children and Adolescents with Borderline Personality Disorder Features

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority - Ashwin Nayak

Ashwin Nayak University of Waterloo April 4, 2011 Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completel

From playlist Mathematics

Solve a Recurrence Relation Using the Telescoping Technique

This video explains how to solve a recurrence relation using the method of telescoping. mathispower4u.com

From playlist Sequences (Discrete Math)

Miller's recurrence algorithm

Related pages