This lesson covers the numerical method of root finding for equations with one variable. The main focus of this lesson is not the analytical method of root finding, but the numerical method as it can be applied to any function type. As such, it is more so an approximation of the root value rather than solving for it directly.
The first topic, Functions, Graphs, and Roots, is more of a refresher topic that covers basic high school math. You may skip it should you wish to.
Polynomials
The term “polynomial” is a general representation of mathematical expressions consisting of variables and coefficients. It involves operations of addition, subtraction, multiplication, and non-negative integer exponentiation of variables.
Some example of valid polynomials include:
- \(x+1\)
- \(5xy+2x\)
- \(x^2+3x-4\)
A polynomial has three distinct parts. They are:
- Variables
- Coefficients
- Exponents
Variable
- Value unknown
- Usually denoted by \(x, y, z \)
Coefficient
- A constant that scales the value of each term.
- Usually denoted by \(a, b, c, p, q, r \) if unknown
Exponent
- A constant that exponentiates the variable instead of multiplying it.
- Usually denoted by \(m, n \) if unknown
Let’s take a look at a simple polynomial: \(3x^2 + x -1 \)
Variable(s): x
Coefficient(s): [3 1 -1]
Exponent(s): [2 1 0]
| Polynomial | Degree |
| \(3x+1 \) | \(1 \) |
| \(4x^3+5x^2-8x+1 \) | \(3 \) |
| \(3x^7+x^5-9x \) | \(7 \) |
In NM Dev, a polynomial is represented by the class Polynomial. For example, to
represent this polynomial: \(p(x)=x^4-10x^3+35x^2-50x+24 \), we construct
a Polynomial instance, supplying the constructor with the coefficients starting from
the highest order term.
%use s2
// a polynomial P(x) = (x-1)(x-2)(x-3)(x-4) = x^4 - 10x^3 + 35x^2 - 50x + 24
val myPoly: Polynomial = Polynomial(1.0, -10.0, 35.0, -50.0, 24.0)
// myPoly is a polynomial of degree 4
println(myPoly)
Output: 1.00(x^4)-10.00(x^3)+35.00(x^2)-50.00(x^1)+24.00
Functions
Functions can be thought of as a converter which receives at least one input value and returns only one output value.
The general form of a function can be written as:
\(f(x_1, x_2 \ldots x_n)=y \)
where \(x_1 \)…\(x_n \) are the \(n \) inputs and \(y \) is the output.
Since we’re only dealing with one variable, \(n=1 \), our function can be simplified to \(f(x)=y \).
Inner workings of a function
The output of a function is computed using a series of operations on the given input(s).
Some functions could be:
\(g(x) = 4x+5 \) (linear)
\(h(x) = 7x^2-2x+9 \) (quadratic)
\(q(x) = e^x-5 \) (exponential* not covered in this lesson)
Domains and Ranges
Every function has a domain and a range over which the function is valid.
Domain
Some functions like \(f(x)=3x+1 \) have a domain that extends throughout the whole real line, meaning the domain \(D_f=(-\infty, \infty) \). Alternatively, it can be said that \(f(x) \) is valid \(\forall x \in \mathbb{R} \)
While most functions have domains \(D=(-\infty, \infty) \), some functions have domains that do not encompass all real numbers.
| Function | Domain | Domain (Set Notation) |
| \(f(x)=3x+1 \) | \(D_f=(-\infty, \infty) \) | \(\mathbb{R} (\forall x \in \mathbb{R}) \) |
| \(g(x)=ln(x) \) | \(D_g=(0, \infty) \) | \({x>0, x \in \mathbb{R}} \) |
| \(h(x)=1/(x-1) \) | \(D_h=(-\infty, 1)\cap(1, \infty) \) | \({x \neq 1, x \in \mathbb{R}} \) |
Range
The range of a function is the region over which a valid output can be obtained given the specified domain.
Here are the ranges for some functions:
| Function | Range | Range (Set Notation) |
| \(f(x)=3x+1 \) | \(R_f=(-\infty, \infty) \) | \(\mathbb{R} \) |
| \(g(x)=e^x \) | \(R_g=(0, \infty) \) | \({g(x)>0, g(x) \in \mathbb{R}} \) |
| \(h(x)=1/(x-1) \) | \(R=(-\infty, 0) \cap (0, \infty) \) | \({g(x) \neq 0, g(x) |
In NM Dev, a function is represented by the interface UnivariateRealFunction.
Typically, we use the class AbstractUnivariateRealFunction to simplify
implementation.. For example, to represent this function: \(f(x) = xsin(x) -3 \), we
construct an instance of AbstractUnivariateRealFunction
%use s2
UnivariateRealFunction f = new AbstractUnivariateRealFunction() {
@Override
public double evaluate(double x) {
return Math.sin(x) * x - 3;
}};
System.out.println("f(1) = " + f.evaluate(1.));
Graphs and Roots
Any function can be plotted on a graph with the x-axis being the input and the y-axis being the output. In doing so, graphs serve as a visual representation for functions and mathematical equations.
Roots
By definition, the point at which a graph intersects the x-axis is considered a root. As \(y=f(x)=0 \), the x-value at that point is a solution to the equation \(f(x)=0 \).
Finding roots also allow for the factorization of polynomial functions.
The graph above has two roots as \(f(-2)=0 \) and \(f(2)=0 \). This allows the function \(f(x)=x^2-4 \) to be rewritten as \(f(x)=(x-2)(x+2) \).
In general, for any singular-input polynomial function \(f(x) \) that has an output value of 0 (i.e. \(f(x)=0 \)), the function can be re-written as \(f(x)=(x-x_1)(x-x_2)(…)(x-x_n) \) for a n-degree polynomial.