eryar@163.com

Abstract. A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x)=0, for a given function f. Such an x is called a root of the function f. In OpenCASCADE math package, implemente Newton-Raphson method to find the root for a function. The algorithm can be used for finding the extrema value for curve or surface, .i.e Point Inversion, find the parameter for a point on the curve or surface. The paper focus on the usage of OpenCASCADE method and its application.

Key Words. OpenCASCADE, Extrema, Newton-Raphson, Root-Finding, FunctionRoot

1. Introduction

2.Numerical Methods

v 秦九韶法；

v 二分法；

v 迭代法；

v 牛顿法Newton’s Method；

v 弦截法；

v 抛物线法；

v 林士谔－赵访熊法；

Newton法在单根邻近收敛快，具有二阶收敛速度，但Newton法对初值要求比较苛刻，即要求初值选取充分靠近方程的根，否则Newton法可能不收敛。扩大初值的选取范围，可采用Newton下山法。

Newton’s Method的实现原理的演示动画如下图所示：

Figure 2.1 Newton’s Method(Newton-Raphson)

Figure 3.2 Newton-Raphson Method

Newton法对初值x0要求苛刻，在实际应用中往往难以满足。Newton下山法是一种降低对初值要求的修正Newton法。

v 求解线性代数方程的根的算法；

v 查找方程极小值的算法；

v 查找非线性方程（组）的根；

v 查找对角矩阵的特征值及特征向量的算法；

```/*
*
*        File    : Main.cpp
*        Author  : eryar@163.com
*        Date    : 2014-10-20 18:52
*        Version : 1.0v
*
*    Description : Test OpenCASCADE function root algorithm.
*
*      Key words : OpenCASCADE, Newton-Raphson, Root-Finding Algorithm, FunctionRoot
*/

#define WNT

#include <Precision.hxx>

#include <math_FunctionWithDerivative.hxx>

#include <math_BissecNewton.hxx>
#include <math_FunctionRoot.hxx>
#include <math_NewtonFunctionRoot.hxx>

#pragma comment(lib, \"TKernel.lib\")
#pragma comment(lib, \"TKMath.lib\")

class TestFunction : public math_FunctionWithDerivative
{
public:
virtual Standard_Boolean Value(const Standard_Real X, Standard_Real& F)
{
F = pow(X, 6) - X - 1;

return Standard_True;
}

virtual Standard_Boolean Derivative(const Standard_Real X, Standard_Real& D)
{
D = 6 * pow(X, 5) - 1;

return Standard_True;
}

virtual Standard_Boolean Values(const Standard_Real X, Standard_Real& F, Standard_Real& D)
{
Value(X, F);

Derivative(X, D);

return Standard_True;
}
};

void TestFunctionRoot(void)
{
TestFunction aFunction;

math_FunctionRoot aSolver1(aFunction, 1.5, 0.0, 0.0, 2.0);

math_BissecNewton aSolver2(aFunction, 0.0, 2.0, 0.0);

math_NewtonFunctionRoot aSolver3(aFunction, 1.5, Precision::Confusion(), Precision::Confusion());

std::cout << aSolver1 << std::endl;
std::cout << aSolver2 << std::endl;
std::cout << aSolver3 << std::endl;
}

int main(int argc, char* argv[])
{
TestFunctionRoot();

return 0;
}```

v math_FunctionRoot：即Newton-Raphson法；

v math_BissecNewton：是Newton-Raphson和二分法的组合算法；

v math_NewtonFunctionRoot：Newton Method；

Figure 3.1 Root-Finding result of OpenCASCADE

4.Application

Figure 4.1 math_FunctionWithDerivative class diagram

v 如果已知点P在给定精度内位于曲线上，则用强凸包性确定候选的段，对于一般的点到曲线的投影问题，则选择所要的段作为候选段；

v 在每个候选段上，计算n个按参数等间隔分布的点。计算出所有这些点和点P的距离，选择其中距点P最近的点的参数作为u0。点数n一般利用某种启发的方法来选择。

Figure 4.2 Point projection and Point inversion

Figure 4.3 class diagram for point inverstion

```Standard_Boolean Extrema_FuncExtPC::Value (const Standard_Real U, Standard_Real& F)
{
if (!myPinit || !myCinit) Standard_TypeMismatch::Raise();
myU = U;
Vec D1c;
Tool::D1(*((Curve*)myC),myU,myPc,D1c);
Standard_Real Ndu = D1c.Magnitude();
if (Ndu <= Tol) { // Cas Singulier (PMN 22/04/1998)
Pnt P1, P2;
P2 = Tool::Value(*((Curve*)myC),myU + delta);
P1 = Tool::Value(*((Curve*)myC),myU - delta);
Vec V(P1,P2);
D1c = V;
Ndu = D1c.Magnitude();
if (Ndu <= Tol) {

if(Ndu  <= Tol)
return Standard_False;
}
}

Vec PPc (myP,myPc);
F = PPc.Dot(D1c)/Ndu;
return Standard_True;
}
//=============================================================================

Standard_Boolean Extrema_FuncExtPC::Derivative (const Standard_Real U, Standard_Real& D1f)
{
if (!myPinit || !myCinit) Standard_TypeMismatch::Raise();
Standard_Real F;
return Values(U,F,D1f);  /* on fait appel a Values pour simplifier la
sauvegarde de l\'etat. */
}
//=============================================================================

Standard_Boolean Extrema_FuncExtPC::Values (const Standard_Real U, Standard_Real& F, Standard_Real& D1f)
{
if (!myPinit || !myCinit) Standard_TypeMismatch::Raise();
myU = U;
Vec D1c,D2c;
Tool::D2(*((Curve*)myC),myU,myPc,D1c,D2c);

Standard_Real Ndu = D1c.Magnitude();
if (Ndu <= Tol) {// Cas Singulier (PMN 22/04/1998)
Pnt P1, P2;
Vec V1;
Tool::D1(*((Curve*)myC),myU+delta, P2, V1);
Tool::D1(*((Curve*)myC),myU-delta, P1, D2c);
Vec V(P1,P2);
D1c = V;
D2c -= V1;
Ndu = D1c.Magnitude();
if (Ndu <= Tol) {
myD1Init = Standard_False;
return Standard_False;
}
}

Vec PPc (myP,myPc);
F = PPc.Dot(D1c)/Ndu;
D1f = Ndu + (PPc.Dot(D2c)/Ndu) - F*(D1c.Dot(D2c))/(Ndu*Ndu);

myD1f = D1f;
myD1Init = Standard_True;
return Standard_True;
}```

```/*
*
*        File    : Main.cpp
*        Author  : eryar@163.com
*        Date    : 2014-10-20 18:52
*        Version : 1.0v
*
*    Description : Test OpenCASCADE function root algorithm.
*
*      Key words : OpenCascade, Extrema, Newton\'s Method
*/

#define WNT

#include <math_FunctionRoots.hxx>
#include <math_NewtonFunctionRoot.hxx>

#include <Extrema_PCFOfEPCOfExtPC.hxx>

#include <GC_MakeCircle.hxx>

#pragma comment(lib, \"TKernel.lib\")
#pragma comment(lib, \"TKMath.lib\")
#pragma comment(lib, \"TKG3d.lib\")
#pragma comment(lib, \"TKGeomBase.lib\")

void TestExtrema(void)
{
Handle_Geom_Curve aCircle = GC_MakeCircle(gp::XOY(), 2.0);

Extrema_PCFOfEPCOfExtPC aFunction(aCircle->Value(0.123456789), aCurve);

math_FunctionRoots aSolver1(aFunction, -2.0, 2.0, 10);
math_NewtonFunctionRoot aSolver2(aFunction, 0.0, 0.0, 0.0);

aSolver1.Dump(std::cout);
std::cout << \"========================================\" << std::endl;
aSolver2.Dump(std::cout);
}

int main(int argc, char* argv[])
{
TestExtrema();

return 0;
}```

5.Conclusion

Newton法可以选作对导数能有效求值，且导数在根的邻域中连续的任何函数方程的求根方法。Newton法在单根邻近收敛快，精度高，具有二阶收敛速度，但Newton法对初值要求比较高，即要求初值选取充分靠近方程的根，否则Newton法可能不收敛。

6. References

1. 数学手册编写组. 数学手册. 高等教育出版社. 1979

2. 赵罡，穆国旺，王拉柱译. 非均匀有理B样条. 清华大学出版社. 2010

3. Les Piegl, Wayne Tiller. The NURBS Book. Springer-Verlag. 1997

4. 易大义，沈云宝，李有法编. 计算方法. 浙江大学出版社. 2002

5. 易大义，陈道琦编. 数值分析引论. 浙江大学出版社. 1998

6. 李庆杨，王能超，易大义.数值分析.华中理工大学出版社. 1986

7. 同济大学数学教研室. 高等数学(第四版). 高等教育出版社. 1996

8. Newton\’s Method video:

http://v.163.com/movie/2006/8/T/V/M6GLI5A07_M6GLLGSTV.html