CS335 Study Guide - Final Guide: Stochastic Calculus, Mathematical Induction, Numerical Analysis

• School: University of Waterloo
• Department: Computer Science
• Course: CS335
• Professor: Zhiyong Liu

Document Summary

A sequence of numbers is an ordered list written in the form (x0, x1, x2, . For example, en = ren 1 for n > 0 (where r is a constant) is a recurrence relation. We can solve this recurrence by noting that en = ren 1 = r (ren 2) = . Suppose xn = rxn 1 + c for n > 0 (1) (2) where r and c are constants and that x0 is given. Let xn denote the exact solution and xn denote an approximation. Let en xn xn denote the error at the n-th step. We assume xn follows the same recurrence as xn (2) for n > 0. That is, xn = rxn 1 + c. (3) We assume that the initial value is perturbed by a constant > 0. Recall the solution (1) to the above recurrence. Stability dictates that errors decay as n .