this video will assume you have some knowledge of bisection method for solving a single equation
check out my video if you haven't already
harvey and stenger came up with a 2d version of bisection
and then a 3d version was developed by sikorski. sikorski and stenger were joined by eiger coming
up with a more general version of bisection citing specifically this paper by kearfott
this video focused on the 2d version by harvey and stenger i do want to point out two other
quick papers though kearfott wrote another paper about journalist bisection in general
and then vrahatis wrote an excellent paper about a new version of a generalized bisection
each of these methods of bisections use different geometries and topologies when solving a system
the simplex approach worked best for dimensions of five or fewer
this was in 1984 and the nd polyhedron approach worked best for dimensions of 10
or fewer and this was in 1988 so those numbers should probably be higher now
the 2d approach uses a test to determine if a point is inside a triangle
they then describe an algorithm for finding that solution using bisecting triangles
note that this video will focus on a simplified version of the algorithm described in the paper
let's evaluate this system of nonlinear equations i'm going to color it in
in a special way each of these colors represent a different sign combination of the function
notice that at each of our solutions we have all four color combinations
let's start using these four points that have a different color combination
we'll then connect them to have two triangles
our solution is in that upper triangle but we have no idea where that point exactly is
let's evaluate our function at each of those points
giving this mapping or transformation of our original points
i'll label them as primes let's connect those in the same way
giving two triangles our solution is at zero zero and we know where this point is
now we just need a way to figure out which triangle contains their point
harvey and stenger came up with what is known as the L test
which looks like this note you actually don't have to use this
specific test to figure out if a point is inside a triangle here's another version
going back to our triangle examples let's just focus on one triangle
then if we draw points to that center point which we'll just call theta and compute the
areas around that the areas of the whole should be equal to the areas of the sum of its parts
here's an example with the point outside our triangle where our areas don't match up
you can figure out the area by using heron's formula labeling each of our lengths as a
b and c computing the semi-perimeter and plugging them into this formula of course
this is just one version you could take the determinate approach using this formula
which comes from this equation with a determinant again the choice is really up to you
one thing to know with the area approach is that you probably won't get exactly
equal to in terms of summation so go with an epsilon approach if you're going to do that
you also don't necessarily need to use area you could take a convex hull method
for finding if a point is inside of a triangle i actually recommend using harvey stenger's test
but you could come up with some other test to figure out if a point is inside a triangle
regardless of the test we know that our point zero zero is in the triangle
a prime b prime c prime which maps back to a b and c
then we evaluate the midpoint d between our longest edge in this case ac
at this point then bisect our triangles in two
and restart the process we'll stop whenever our center of the triangle is less than epsilon in
the norm or our longest side length is less than epsilon or reach a maximum number of iterations
i wrote a program to visualize these triangles rather than me having to
create them in slides here's the first step
the second step
and the third notice this idea of bisecting triangles always seems to work
i then iterated a bunch more times let's zoom in
here i'll stop the iterations and our final solution will be the center of that triangle
let's look at the algorithm one more time we started with four points making sure we
had different sign combinations and then divide them into two triangles
then we test it to see if our point was in our first triangle
in this case i use the L test if it was we put r into t if it wasn't we put s into t
and then rotate the triangle so that our first edge is the longest one
and call our points a b and c then figure out the center of our triangle calling it e dividing our
longest edge into point d and developing two new triangles with bisection then check if our final
point in the center is small enough in terms of the norm or our longest distance is small enough
when it isn't we continue our bisection approach when it is let e be our answer and stop
recall that we started with these four points we didn't necessarily have to pick these four
we could have chosen these four each of them having that different sign combination
the trouble though is that now we don't actually have a solution in either triangle
our simplified start doesn't guarantee a solution
you could have an alternate starting condition that says pick a triangle that contains
a solution but that's harder to find than just four points with different signs
going back to harvey and stenger's original paper i mentioned that we
covered a simplified version of their algorithm here's what their algorithm actually looks like
and you can imagine why we chose the simplified version their fuller algorithm starts by creating
a large polygon that's many-sided that it would enclose our solution by then dividing
it into triangles and measuring the angles of the triangles to figure out the topology afterwards
combining them to create parallelograms and then doing backtracking steps if you don't end up
finding a solution and many other steps i'll link to the paper in the description if you are curious
now you might be wondering what about a hybrid version similar to brent-dekker in which you
combined by section with secant method well you could imagine a generalized version of secant
method combined with generalized bisection which identified areas and triangles and if the secant
step ever was outside of your triangle you'd force a bisection you could do something similar with
newton-bisection hybrid combining generalized newton's method with generalized bisection
to recap this lesson covered a method of bisecting triangles to solve systems of nonlinear equations
with the key element being that we could figure out if a point was inside of our triangle like
zero note that our area is halved each iteration so essentially converging linearly
keep in mind that our simplified version of the algorithm needs to be careful where you choose
your starting points there are also different ways to hybrid bisection with other methods
harvey and stenger also proved in their paper sufficient conditions
for convergence which i am not going to go over the code that i wrote will be hosted on github
as always thank you for watching this lesson was probably one of the hardest to put together
even though the concept of bisecting triangles sounds like a simple idea on paper
if you're curious i already have a lesson on generalized false position method
that i'll have a card to here in the end screen again thank you for watching