O'Reilly logo

Mastering Algorithms with C by Kyle Loudon

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Description of the Solution of Equations

One of the most fundamental problems in scientific computing is solving equations of the form f (x) = 0. This is often referred to as finding the roots, or zeros, of f (x). Here, we are interested in the real roots of f (x), as opposed to any complex roots it might have. Specifically, we will focus on finding real roots when f (x) is a polynomial.

Finding Roots with Newton's Method

Although factoring and applying formulas are simple ways to determine the roots of polynomial equations, a great majority of the time polynomials are of a large enough degree and sufficiently complicated that we must turn to some method of approximation. One of the best approaches is Newton's method. Fundamentally, Newton's method looks for a root of f (x) by moving closer and closer to it through a series of iterations. We begin by choosing an initial value x = x 0 that we think is near the root we are interested in. Then, we iterate using the formula:

image with no caption

until xi + 1 is a satisfactory approximation. In this formula, f (x) is the polynomial for which we are trying to find a root, and f ' (x) is the derivative of f (x).

Computing the Derivative of a Polynomial

The derivative of a function is fundamental to calculus and can be described in many ways. For now, let's simply look at a formulaic description, specifically for polynomials. To compute the derivative of a polynomial, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required