Curves
Curves - Implicit Representation
- Most curvest can be represented implicitly:
- \[f(x, y) = 0\]
- Examples:
- \[ax + by + c = 0\]
- \[x^2 + y^2 - r^2 = 0\]
- In 3D, surfaces are represented as:
- \[f(x, y, z) = 0\]
Curves - Parametric Representation
- The value of each component (x, y, z) depends on an independent variable, u (the parameter).
- \[p(u) = \begin{bmatrix} x(u) \\ y(u) \\ z(u) \end{bmatrix}\]
-
\[\frac{dp(u)}{du} = \begin{bmatrix} \frac{dx(u)}{du} \\ \frac{dy(u)}{y(u)} \\ \frac{dz(u)}{z(u)} \end{bmatrix}\]
- Derivative : Direction = tangent, Magnitude = speed that curve changes with u
Criteria for choosing a representation
- Parametric forms are not unique. Many different representations are possible for a single curve.
- Criteria for a good representation:
- Local control of shape
- Smoothness and continuity
- Ability to evaluate derivatives
- Stability
- Ease of Rendering
- Parametric curves that are polynomials in u satisfy many of these criteria:
- \[x(y) = c_0 + c_1 u + c_2 u^2 + \cdots + c_n u^n = \sum_{k=0}^n c_ku^k\]
Matrix Equation for parametric curve
- We can write the 3 euqations for x(u), y(u), and z(u) in one matrix equation:
- \[p(u) = \begin{bmatrix} x(u) \\ y(u) \\ z(u) \end{bmatrix} = \begin{bmatrix} \sum_{k=0}^n u^k c_{xk} \\ \sum_{k=0}^n u^k c_{yk} \\ \sum_{k=0}^n u^k c_{zk} \end{bmatrix} = \sum_{k=0}^n u^k \begin{bmatrix} c_{xk} \\ c_{yk} \\ c_{zk} \end{bmatrix} = \sum_{k=0}^n u^k c_k\]
Degree of the Polynomial
- Tradeoff:
- High degree can have rapid changes and lots of turns, but it requires more computation and curve may not be as smooth.
- Low degree means a smoother curve, but it may not fit the data as well.
- Compromise: Use low degree polynomials with short curve segments. Cubic polynomial work well.
Multiple curve segments
- We usually want to define a curve segment between two endpoints. We define the curve between u=0 and u=1, so that:
- $p(0) = p_0$ and $p(1) = p_1$
- Longer curves are composed of multiple segments. We would like the connection between curves to be as smooth as possible.
Interpolation
- If one point provides 3 equations and 12 unknowns, then 4 points provide 12 equations with 12 unknowns.
- We can choose any value of u to correspond to the 4 points, so we will choose to divide the interval 0 to 1 evenly(0, 1/3, 2/3, 1).
PCA
Principal Components
- All principal components(PCs) start at the origin
- First PC is direction of maximum variance from origin
- Subsequent PCs are orthogonal to 1st PC and describe maximum residual variance
Principal Component Analysis
- For an arbitrary set of N vertices $P_1, P_2, …, P_N$
- Mean position : $m = \frac{1}{N} \sum_{i=1}^N P_i$
- 3x3 covariance matrix : $C= \frac{1}{N} \sum_{i=1}^N(P_i - m ) (P_i - m)^T$:
- Represents the corrleation between each pair of the $x,y,$ and $z$ coordinates
- Covariance matrix entries:
- \[C_{11} = \frac{1}{N} \sum_{i=1}^N(x_i - m_x)^2, C_{12} = C_{21} = \frac{1}{N} \sum_{i=1}^N (x_i - m_x)(y_i - m_y)\]
- \[C_{22} = \frac{1}{N} \sum_{i=1}^N(y_i - m_y)^2, C_{13} = C_{31} = \frac{1}{N} \sum_{i=1}^N (x_i - m_x)(z_i - m_z)\]
- \[C_{33} = \frac{1}{N} \sum_{i=1}^N(z_i - m_z)^2, C_{23} = C_{32} = \frac{1}{N} \sum_{i=1}^N (y_i - m_y)(z_i - m_z)\]
- An entry of zero : no corrleation
-
$C$ is diagonal matrix : three coordinates are uncorrelated
- We want to transform points so that the covariance matrix is diagonal
- \[\begin{aligned}C' &= \frac{1}{N} \sum_{i=1}^N(AP_i - Am)(AP_i - Am)^T \\ &= \frac{1}{N} \sum_{i=1}^N A(P_i - m)(P_i - m)^T A^T \\ &= ACA^T \end{aligned}\]
- Find $A$ using eigenvectors:
- Rows of $A$ are unit eigenvectors sorted by eigenvalues in decreasing order
Higher Diemnsions
- Suppose data poitns are N-dimensional:
- Same procedure applies :$C’ = ACA^T$
- The eigenvectors define a new coordinates:
- eigenvector with largest eigenvalue captures the most variation among training vectors
- eigenvector with smallest eigenvalue has least variation
- We can compress the data by only using the top few eigenvectors:
- corresponds to choosing a “linear subspace”
Decomposition
Trianglular Systems
- Lower triangular matrix $L$:
- Square matrix for which $L_{ij} = 0$ when $i < j$
- Linear system $Lx = r$
- \[\begin{bmatrix} L_{11} & 0 & \cdots & 0 \\ L_{21} & L_{22} & \cdots 0 \\ \vdots & \vdots & \ddots & \vdots \\ L_{n1} & L_{n2} & \cdots & L_{nn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \\ \vdots \\ r_n \end{bmatrix}\]
- Forward substitution:
- \[x_i = \frac{1}{L_{ii}} ( r_i - \sum_{k=1}^{i-1} L_{ik}x_k)\]
- Upper triangle
- Square matrix for which $U_{ij} = 0$ when $i > j$
- \[\begin{bmatrix} U_{11} & U_{12} & \cdots & U_{1n} \\ 0 & U_{22} & \cdots U_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & U_{nn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \\ \vdots \\ r_n \end{bmatrix}\]
- Backward substitution:
- \[x_i = \frac{1}{U_{ii}} ( r_i - \sum_{k=i+1}^{n} U_{ik}x_k)\]
LU Decomposition
- $LU = M$
- \[\begin{bmatrix} L_{11} & 0 & \cdots & 0 \\ L_{21} & L_{22} & \cdots 0 \\ \vdots & \vdots & \ddots & \vdots \\ L_{n1} & L_{n2} & \cdots & L_{nn} \end{bmatrix} \begin{bmatrix} U_{11} & U_{12} & \cdots & U_{1n} \\ 0 & U_{22} & \cdots U_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & U_{nn} \end{bmatrix} = \begin{bmatrix} M_{11} & M_{12} & \cdots & M_{1n} \\ M_{21} & M_{22} & \cdots & M_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ M_{n1} & M_{n2} & \cdots & M_{nn} \end{bmatrix}\]
- \[M_{ij} = \sum_{k=1}^i L_{ik} U_{kj}, \text{ if } i \le j\]
- \[M_{ij} = \sum_{k=1}^j L_{ik} U_{kj}, \text{ if } i \ge j\]
- $Mx = r \Rightarrow LUx = r$:
- Let $Ux = y$
- Solve $Ly = r$
- Solve $Ux = y$
- Doolittle’s Method:
- $L_{ii} \equiv 1, i =1, 2, …, n$
- We can express L and U in one matrix:
- \[D = \begin{bmatrix} U_{11} & U_{12} & U_{13} & \cdots & U_{1n} \\ L_{21} & U_{22} & U_{23} & \cdots & U_{2n} \\ L_{31} & L_{32} & U_{33} & \cdots & U_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ L_{n1} & L_{n2} & L_{n3} & \cdots & U_{nn} \end{bmatrix}\]
- Solve U and L for each column j for top to bottom:
- \[U_{1j} = M_{1j}; L_{i1} = \frac{M_i1}{U_{11}}\]
- \[U_{ij} = M_{ij} - \sum_{k=1}^{i-1} L_{ik} U_{kj}, \text{ if } i > 1\]
- \[L_{ij} = \frac{1}{U_{jj}} ( M_{ij} - \sum_{k=1}^{j - 1} L_{ik} U_{kj}), \text{ if } j > 1\]
Error Reduction
- Suppose we solve a linear system $Mx = r$:
- If we obtained a solution $x= x_0$, $x_0$ usually slightly different from the true solution due to round-off error
- Thus $Mx_0 = r_0$:
- $M(x + \Delta x) = r + \Delta r$, where $\Deltax = x_0 - x, \Deltar = r_0 - r$
- $M \Delta x = \Delta r$
- $M \Delta = M x_0 - r$
- solve for the error $\Delta x$ and improve the solution : $x = x_0 - \Delta x$
Matrix Inversion
- Matrix inverse can be computed in a column-by-column method
- \[MM^{-1} = I\]
Iterative
Solving Large Lienar Systems
- Global illumination (Radiosity):
- Solve $B = (I - \rho F)^{-1} E$
- Need to solve for a large matrix
- It takes too much time with conventional methods
Jacobi Method
- Iterative or approximate method
- Solve a linear system $AX=B$
- General formula:
- \[x_i^{(k+1)} = \frac{1}{a_{ii}} ( b_i - \sum_{j \not = i} a_{ij} x_{j}^{(k)}), i=1,2, ...,n\]
- Convergence check:
- $\epsilon_i = \vert \frac{x_i^j x_i^{j-1}}{x_i^j} \vert < \epsilon_s$
Gauss-Seidel Method
- Speed up the convergence
- Use better approximations when possible
- $x_{k+1}$ is a better approximation to $x$ than $x_k$.
- $x_i^{(k+1)} = \frac{1}{a_{ii}} (b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)}), i = 1,2,…,n$
Convergence
- Sufficient condition for convergence:
- Method always converge if the matrix $A$ is diagonally dominant
- Row diagonal dominance: For each row, the absolution value of the diagonal term is greater than the sum of absolute values of other terms
- $\vert a_{ii} \vert > \sum_{i \not = j} \vert a_{ij} \vert$
Relaxation in Gauss-Seidel
- Slight modification for improving convergence
- $x_i^{(k+1)} = \lambda x_i^{(k+1)} + (1 - \lambda) x_i^{(k)}$, $0 < \lambda < 2$:
- If $\lambda = 1$, no changes
- If $0 < \lambda < 1$, underrelaxation helps to make a nonconvergent system converge
- If $1 < \lambda < 2$, overrelaxation to accelerate the converge
Interpolation
Interpolation
- Iterpolation:
- A process of finding a function that passes through a given set of points $(x_i, y_i)$ (data fitting or curve fitting)
- It can be used to estimate variable $y$ corresponding to unknown $x \in [a, b] - { x_i }$
- Extrapolation:
- Estimate variable $y$ corresponding to $x < x_0$ or $x > x_n$
- Purpose of interpolation:
- Replace a set of data points ${(x_i, y_i)}$ with a function given analytically.
- Approximate functions with simpler ones, usually polynomials or ‘piecewise polynomials’.
Linear Interpolation
- Interpolation with straight line:
- Let two data poitns $(x_0, y_0)$ and $(x_1, y_1)$ be given. There is a unique straight line passing through these points. We can write the formula for a straight line as:
- \[P_1(x) = y_0 + (\frac{y_1 - y_0}{x_1 - x_0})(x - x_0)\]
- Let two data poitns $(x_0, y_0)$ and $(x_1, y_1)$ be given. There is a unique straight line passing through these points. We can write the formula for a straight line as:
Quadratic Interpolation
- We want to find a polynomial:
- $P_2(x) = a_0 + a_1 x + a_2 x^2$
- which satisfies:
- $P_2(x_i) = y_i, i = 0, 1, 2$
- for given data points $(x_0, y_0), (x_1, y_1), (x_2, y_2)$
- Lagrange interpolation:
- $P_2(x) = y_0 L_0(x) + y_1 L_1(x) + y_2 L_2(x)$
- with:
- $L_0(x) = \frac{(x - x_1)(x - x_2)}{x_0 - x_1)(x_0 - x_2)}$
- $L_1(x) = \frac{(x - x_0)(x - x_2)}{x_1 - x_0)(x_1 - x_2)}$
- $L_2(x) = \frac{(x - x_0)(x - x_1)}{x_2 - x_0)(x_2 - x_1)}$
- Uniqueness:
- Can there be another polynomial, call it $Q(x)$, for which:
- $deg(Q) \le 2$
- Let $R(x) = P_2(x) - Q(x)$
- From the properties of $P_2$ and $Q$, we have $deg(R) \le 2$
- $R(x_i) = P_2(x_i ) - Q(x_i) = y_i - y_i = 0$
- Three zeros for quadratic function
- So, $R(x) = 0$ for all x, $Q(x) = P_2(x)$ for all x
- Can there be another polynomial, call it $Q(x)$, for which:
Higher Degree Interpolation
- Polynomail function of degree $n$:
- $deg(P_n) \le n$
- $P_n(x_i) = y_i, i = 0, 1, …, n$
- with data points $(x_0, y_0), …, (x_n, y_n)$
- Lagrange interpolation:
- $P_n(x) = y_0 L_0(x) + y_1 L_1(x) + \cdots + y_n L_n(x)$
- $L_k(x) = \frac{(x - x_0) … (x - x_{k-1})(x - x_{k+1}) … (x - x_n)}{(x_k - x_0) … (x_k - x_{k-1})(x_k - x_{k+1})…(x_k - x_n)}$
Newton Polynomials
- It is sometimes useful to find $P_1(x), P_2(x), …, P_N(x)$
- Lagrange polynomials:
- No constructive relationship between $P_{N-1}(x)$ and $P_N(x)$
- Newton polynomials:
- Recursive pattern
- $P_N(x) = P_{N-1}(x) + g_N(x)$
- $g_N(x) = a_N(x - x_0)(x - x_1) … (x - x_{N-1})$
- To find $a_k$ for all polynomials $P_1(x), P_2(x), …, P_N(x)$ that approximate a given function $f(x)$
- $P_k(x)$ is based on the centers $x_0, x_1, …, x_k$
- $a_1$ : slope of the line between $(x_0, f(x_0))$ and $(x_1, f(x_1))$
General Divided Differnce
- Given $n + 1$ distinct points $x_0, …, x_n$, with $n \ge 2$, define:
- $$f[x_0, …, x_n] = \frac{f[x_1, …, x_n] - f[x_0, …, x_{n-1}]}{x_n - x_0}$
- $$f[x_0, …l, x_n] = \frac{1}{n!} f^{(n)}(xc)$
- for some $c$ intermediate to the points ${x_0, …, x_n }$
Spherical Linear Interpolation
- \[q(t) = \frac{sin \theta (1 - t)}{sin \theta} q_1 + \frac{sing \theta t}{sin \theta} q_2\]
Bilinear Interopolation
- \[f(R_1) \approx \frac{x_2 - x}{x_2 - x_1} f(Q_{11}) + \frac{x - x_1}{x_2 - x_1} f(Q_{21})\]
- \[f(R_2) \approx \frac{x_2 - x}{x_2 - x_1} f(Q_{12}) + \frac{x - x_1}{x_2 - x_1} f(Q_{22})\]
- \[f(P) \approx \frac{y_2 - y}{y_2 - y_1} f(R_1) + \frac{y - y_1}{y_2 - y_1} f(R_2)\]
Least Squares
Least-Squares Line
- Data points $(x_1, y_1), …, (x_N, y_N), {x_k }$ are distinct
- Numerical method is to determine $y=f(x)$
- Lienar approximation: $y = f(x) = Ax + B$
- If there is an error in the data points:
- \(f(x_k) = y_k + e_k\),
- where $e_k$ is the error
Errors
- Erros: $e_k = f(x_k) - y_k$ for $1 \le k \le N$
- Norms to measure how far the curve $y=f(x)$ lies from the data
- Maximum error: $E_{\infty} (f) = {max}_{1 \le k \le N} { \vert f(x_k) - y_k }$
- Average error: $E_1 (f) = \frac{1}{N} \sum_{k=1}^N \vert f(x_k) - y_k \vert$
- Root-mean-squre error: $E_2 (f) = ( \frac{1}{N]} \sum_{k=1}^N \vert f(x_k) - y_k \vert ^2)^{1/2}$
- Maximum error is sensitive to extreme data
- Average is often used since it’s easy to compute
- RMS is often used when statistical nature is used
Least-Squares Line
- A best-fitting line is minimizing the rror
- RMS is the traditional choice
- Coefficients of least-squares line $y=Ax + B$ are the solution of the followign linear system:
- \[(\sum_{k=1}^N x_k^2) A + (\sum_{k=1}^N x_k) B = \sum_{k=1}^N x_k y_k\]
- $$\sum_{k=1}^N x_k) A + NB = \sum_{k=1}^N y_k$
- Eror is teh vertical distance between $(x_k, y_k)$ and $(x_k, Ax_k + B)$ and we want minimize their squared sum
- $E(A, B)$ is minimum when the partical derivatives $\partial E / \partial A$ and $\partial E / \partial B$ equal to zero
-
\[\begin{aligned} \frac{\partial E(A, B)}{\partial A} &= \sum_{k=1}^N 2(A x_k + B - y_k)(x_k) \\ &= 2 \sum_{k=1}^N (A x_k^2 + B x_k - x_k y_k) \end{aligned}\]
- \[0 = A \sum_{k=1}^N x_k^2 = B \sum_{k=1}^N x_k - \sum_{k=1}^N x_k y_k\]
- $$\begin{aligned} \frac{\partial E(A, B)}{\partial B} &= \sum^N 2(Ax_k + B - y_k) \ &= 2 \sum_{k=1}^N (A x_k + B - y_k)\end{aligned}$
- \[0 = A \sum_{k=1}^N x_k + NB - \sum_{k=1}^N y_k\]
Power Fit
- Fitting $f(x) = Ax^M$, where $M$ is known
- Least-squares power curve: minimize the RMS (Root-Mean-Square) error:
- \[A = \sum_{k=1}^N x_k^M y_k) / (\sum_{k=1}^N x_k^{2M})\]
- Least-Squares method: minimize $E(A)$:
- \[E(A) = \sum (Ax_k^M - y_k)^2\]
- Solve $E’(A) = 0$:
- \[E'(A) = 2 \sum (A x_k^{2M} - x_k^M y_k)\]
- \[0 = A \sum x_k^{2M} - \sum x_k^M y_k\]
Data Linearization
- Data linearization : process to transform a non-linear relation into a linear relation
Matrix Formulation
- Lienar system:
- $F^TFC = F^TY$ for the coeeficient matrix $C$
Polynomial Fitting
- Polynomial function:
- \[f(x) = c-1 + c_2 x + c_3 x^2 + \cdots + c_{M+1} x^M\]
- Least-squares parabola
Nonlinear Least-Squares Method
- Nonlinear system can be solved with Newton’s Method:
- Time consuming
- Requires good starting values for $A$ and $C$
- Minimize $E(A, C)$ directly using optimization methods
Optimization
- Methods for locating extrema(maxima or minima) of functions
Functions of One Variable
- The function $f$ has a local minimum value at $x=p$, if there exists an open interval $i$ containing $p$ s.t. $f(p) \le f(x)$ for all $ x \in I$
- $f$ has a local maximum value at $x = p$, if there exists an open interval $i$ containing $p$ s.t. $f(x) \le f(p)$ for all $ x \in I$
-
$f$ has a local extremum value at $x=p$, if it has local minimum or maximum value at $x=p$.
- Theorem 1:
- Suppose that $f(x)$ is continuous on $i= [a,b]$ and is differentiable on $(a, b)$:
- If $f’(x) > 0$ for all $x \in 9a, b)$, then $f(x)$ is increasing on $I$.
- If $f’(x) < 0$ for all $x \in (a, b)$, then $f(x)$ is decreasing on $I$.
- Suppose that $f(x)$ is continuous on $i= [a,b]$ and is differentiable on $(a, b)$:
- Theorem 3:
- Suppose that $f(x)$ is continuous on $i= [a,b]$ and $f’(x)$ is defined for all $x \in (a, b)$, except possibly at $x=p$:
- If $f’(x) < 0$ on $(a, p)$ and $f’(x) > 0$ on $(p, b)$, then $f(p)$ is a local minimum.
- If $f’(x) > 0$ on $(a, p)$ and $f’(x) < 0$ on $(p, b)$, then $f(p)$ is a local maximum.
- Suppose that $f(x)$ is continuous on $i= [a,b]$ and $f’(x)$ is defined for all $x \in (a, b)$, except possibly at $x=p$:
- Theorem 4:
- Suppose that $f(x)$ is continuous on $i= [a,b]$ and $f’,f’’$ is defined for all $x \in (a, b)$, Also, $p \in (a, b)$ is a critical point where $f’(p) = 0$:
- If $f’‘(p) > 0$, then $f(p)$ is a local minimum of $f$.
- If $f’‘(p) < 0$, then $f(p)$ is a local maximum of $f$.
- If $f’‘(p) = 0$, then this test is inconclusive.
- Suppose that $f(x)$ is continuous on $i= [a,b]$ and $f’,f’’$ is defined for all $x \in (a, b)$, Also, $p \in (a, b)$ is a critical point where $f’(p) = 0$:
Bracketing Search Methos
- Evaluate the function many times and search for a local minimum/maximum
- To reduce the number of function evaluations, a good strategy is needed for determining where the function is to be evaluated
- Definition:
- The function $f(x)$ is unimodal on $I = [a, b]$, if there exists a unique number $p \in I$ such that:
- $f(x)$ is decreasing on $[a, p]$
- $f(x)$ is increasing on $[p, b]$
- The function $f(x)$ is unimodal on $I = [a, b]$, if there exists a unique number $p \in I$ such that:
Golden Ratio Search
- If $f(x)$ is unimodal on $[a,b]$, then it is possible to replace the interval with a subinterval on which $f(x)$ takes on its miniumum value
- Select two interior points $c < d \Rightarrow a < c < d < b$
- $f(c), f(d) < max(f(a), f(b))$:
- When $f(c) \le f(d)$:
- The minimum must occur in $[a,d]$
- New subinterval $[a, d]$
- When $f(d) < f(c)$:
- The minimum must occur in $[c, d]$
- New subinterval $[c, b]$
- When $f(c) \le f(d)$:
- $c = ra + (1 - r)b$
- $d = (1 - r)a + rb$
- $r = \frac{-1 + \sqrt 5}{2}$
Fibonacci Search
- The value r is not constant on each subinterval
- Number of subintervals (iterations) is predetermined and based on the specified tolerance
- The interior poitns $c_k$ and $d_k$ of the k-th subinterval $[a_k, b_k]$ are:
- $c_k = a_k + (1 - \frac{F_{n-k-1}{F_{n-k}}})(b_k - a_k)$
- $d_k = a_k + \frac{F_{n-k-1}}{F_{n-k}}(b_k - a_k)$
- For a tolerance $\epsilon$, find the smallest value of $n$ such that:
- \[\frac{b_0 - a_0}{F_n} < \epsilon, F_n > \frac{b_0 - a_0}{\epsilon}\]
Multidimensional Optimization
- Find the extremum of a function of several variables:
- Direct method (No derivatives)
- Gradient method (Use derivatives)
Direct Methods - Random Search
- Based on evaluation of the fuction randomly at selected values of the independent variables.
- If a sufficient number of samples are ocnducted, the optimum will be eventually located
- Advantages:
- Works even for discontiuous and nondifferentiable functions.
- Disadvantages:
- As the number of independent variables grows, the task can become onerous.
- Not efficient, it does not account for the behavior of underlying function
Direct Method - Univariate and Pattern Search
- More efficient than random search and still doesn’t require derivative evaluation
- The baisc strategy:
- Change one variable at a time while the other variables are held constant.
- Problem is reduced to a sequence of one-dimensional searches that can be solved by variety of methods
- The search becomes less efficient as you approach the maximum.
Gradient
- Graident of a function $f$, $\nabla f$, tells us:
- $$\nabla f = \begin{bmatrix} \frac{\partial f}{\partial x_1} \ \vdots \ \frac{\partial f}{\partial x_n} \end{bmatrix}$
Hessian Matrix (of Hessian of $f$)
- $$H = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partialx_1 \partial x} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \ \vdots & \vdots & \ddots & \vdots \ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partialx_n^2} \end{bmatrix}$
- Also known as the matrix of second partial derivatives.
- It provides a way to discern if a funciton has reached an optimum or not.
Solution of Nonlinear Equation
Basis of Bisection Method
- An equation $f(x) = 0$, where $f(x)$ is a real continuous function, has at least one root between $x_l$ and $x_u$ if $f(x_l)f(x_u) < 0$.
- If